DEV Community: Amish Singh

The Master Method and it's Intuition

Amish Singh — Wed, 02 Sep 2026 05:23:25 +0000

Most people learn the Master Method as a lookup table: compare $a$ to $b^{d}$ , pick one of three cases, done. The table works, but it's not understood; it's recited. The moment you meet a recurrence that doesn't fit neatly into the memorized shape, the table is useless.

The fix is to never memorize the table at all. Build a recursion tree for the general recurrence

T (n) = a \cdot T (n / b) + O (n^{d})

count the work level by level, and let a single geometric series, built the exact way Tim Roughgarden derives it, tell you which of the three cases you're in and why. Once you've done this once by hand, the "three cases" stop feeling like three separate facts and become one picture viewed from three different angles.

Step 1: Build the tree, one level at a time

At the root (level 0), there is exactly one call, operating on an input of size $n$ , doing $O (n^{d})$ work outside of its recursive calls.

Level 0:        [ n ]                work = n^d

That call makes $a$ recursive calls, each on a subproblem of size $n / b$ . That's level 1:

Level 0:            [ n ]                              work = n^d
Level 1:   [n/b] [n/b] ... [n/b]   (a of them)          work = a·(n/b)^d

The row work already tells you something important: going from level 0 to level 1, the work got multiplied by $a$ (more subproblems) and divided by $b^{d}$ (each subproblem cheaper). Whether the total work grows or shrinks as you go deeper depends entirely on which of those two effects is bigger.

Step 2: The general formula for row j

Generalize the pattern. At level $j$ (counting down from the root, which is level 0):

Number of nodes: each node spawns $a$ children, so level $j$ has $a^{j}$ nodes.
Size per node: the input has been divided by $b$ , $j$ times, so each node holds a subproblem of size $n / b^{j}$ .
Work per node: $(n / b^{j})^{d}$ .

Multiplying nodes by work-per-node gives the total work at level $j$ , call it $W_{j}$ :

W_{j} = a^{j} \cdot (\frac{n}{b ^{j}})^{d} = \frac{a ^{j} \cdot n ^{d}}{b ^{j d}} = n^{d} \cdot (\frac{a}{b ^{d}})^{j}

Define $r = \frac{a}{b ^{d}}$ . This single number is the ratio between consecutive rows of the tree: it is the whole Master Method compressed into one variable. $a$ is the rate at which subproblems multiply going down the tree; $b^{d}$ is the rate at which the work per subproblem shrinks. $r$ is simply which of those two effects wins.

Step 3: Total work is a geometric series

The tree bottoms out when a subproblem reaches size 1, i.e., when $n / b^{j} = 1$ , giving $j = lo g_{b} n$ levels. Summing the row work over every level from the root to the leaves:

T (n) = j = 0 \sum l o g_{b} n n^{d} \cdot r^{j} = n^{d} j = 0 \sum k r^{j}, where k = lo g_{b} n

This is exactly a geometric series, a sum of a constant ratio raised to increasing powers, and its behavior is fully determined by the closed-form geometric sum formula:

j = 0 \sum k r^{j} = \frac{r ^{k + 1} - 1}{r - 1} (r \neq = 1) j = 0 \sum k r^{j} = k + 1 (r = 1)

Everything from here is just plugging in $r = a / b^{d}$ and reading off what dominates.

Case 1: r is less than 1, the sum is bounded by a constant and dominated by the first term

If $a < b^{d}$ , then $r < 1$ . Rewrite the geometric sum for this case as:

\frac{r ^{k + 1} - 1}{r - 1} = \frac{1 - r ^{k + 1}}{1 - r}

Since $0 < r < 1$ , the term $r^{k + 1}$ shrinks toward 0 as $k$ grows; it never grows, no matter how deep the tree is. The entire sum is therefore bounded above by the constant $\frac{1}{1 - r}$ , regardless of how many levels the tree has. The geometric series doesn't blow up with depth. It converges, and the term that matters is the first term of the series (the root), because every later term is a shrinking fraction of it.

Level 0:  [ n ]           work = n^d
Level 1:  [n/b]           work = r · n^d
Level 2:  [n/b²]          work = r² · n^d
             ⋮                    ⋮  (shrinking geometrically)

Conclusion: since the sum is a constant multiple of the root's work, the total cost of the tree is dominated by the root, giving $T (n) = Θ (n^{d})$ .

Case 2: r equals 1, every term is equal and the sum is just the level count

If $a = b^{d}$ , then $r = 1$ , and the geometric sum formula degenerates to $k + 1$ , the number of levels. Every row contributes exactly $n^{d}$ , with no growth and no decay:

Level 0:  [ n ]              work = n^d
Level 1:  [n/b] ... [n/b]    work = n^d
Level 2:  [n/b²] ... [n/b²]  work = n^d
             ⋮                  ⋮  (flat)

Conclusion: since there are $lo g_{b} n + 1$ levels, each contributing $n^{d}$ , the total is $T (n) = Θ (n^{d} lo g n)$ .

Case 3: r is greater than 1, the sum is dominated by the last term

If $a > b^{d}$ , then $r > 1$ . Now the geometric sum

\frac{r ^{k + 1} - 1}{r - 1}

grows without bound as $k$ grows. Crucially, it is dominated by its largest term, which is the final term of the series, $r^{k}$ , not the first one. This is the mirror image of Case 1: when $r > 1$ , each successive term is larger than the one before it by a factor of $r$ , so the sum is within a constant factor of its biggest term. Pulling $r^{k}$ out of every term in the sum:

j = 0 \sum k r^{j} = r^{k} i = 0 \sum k (\frac{1}{r})^{i} = O (r^{k})

since $\frac{1}{r} < 1$ , that inner sum falls back into Case 1's bounded regime: it's just some constant. So the total work is dominated by the last level of the tree, the leaves, not the root.

Level 0:  [ n ]                    work = n^d
Level 1:  [n/b] [n/b] [n/b] [n/b]  work = r · n^d
Level 2:  [n/b²] × a²              work = r² · n^d
             ⋮                        ⋮  (growing geometrically)
Level k:  [1] × a^k                work = r^k · n^d   ← dominant term

Don't leave that dominant term as $r^{k} \cdot n^{d}$ ; simplify it all the way down. Recall $k = lo g_{b} n$ , which means $b^{k} = n$ . Substitute $r = a / b^{d}$ and expand step by step:

r^{k} \cdot n^{d} = (\frac{a}{b ^{d}})^{k} \cdot n^{d} = \frac{a ^{k}}{( b ^{k} ) ^{d}} \cdot n^{d} = a^{k} \cdot (\frac{n}{b ^{k}})^{d}

Now use $b^{k} = n$ to collapse the fraction:

a^{k} \cdot (\frac{n}{b ^{k}})^{d} = a^{k} \cdot (\frac{n}{n})^{d} = a^{k} \cdot 1^{d} = a^{k}

So the dominant term is just $a^{k}$ , plain and simple: the number of leaves. Substituting $k = lo g_{b} n$ back in, and using the identity that swapping the base and the exponent of a power-of-a-log leaves the value unchanged,

a^{k} = a^{l o g_{b} n} = n^{l o g_{b} a}

Conclusion: since the sum is dominated by the leaf level, and that leaf-level term simplifies to exactly $a^{k} = n^{l o g_{b} a}$ , $T (n) = Θ! (n^{l o g_{b} a})$ .

Why that exponent is exactly the leaf count

That final expression, $n^{l o g_{b} a}$ , isn't an arbitrary algebra trick. It is, literally, the number of leaves in the tree. The derivation above showed exactly that: the dominant term collapsed to $a^{k}$ , the leaf count, and rewriting $k$ as $lo g_{b} n$ turned that leaf count into $n^{l o g_{b} a}$ .

So in Case 3, when the tree's total cost is dominated by its bottom row, what you're really computing is "how many leaves does this tree have?", and the answer to that question, $n^{l o g_{b} a}$ , is the running time. The formula isn't describing some abstract growth rate. It's counting boxes at the bottom of the picture you already drew.

Worked example: fixing b and d, varying only a

To see all three cases as one continuous family, fix $b = 2$ and $d = 1$ (so the base recurrence is $T (n) = a \cdot T (n /2) + O (n)$ ) and vary only $a$ .

$a = 1 \Rightarrow r = \frac{1}{2} < 1$ . $T (n) = T (n /2) + O (n)$ . Row work shrinks geometrically: $n, n /2, n /4, \dots$ . Bounded by the root. $T (n) = Θ (n)$ .

$a = 2 \Rightarrow r = 1$ . $T (n) = 2 T (n /2) + O (n)$ , merge sort. Row work is flat: $n, n, n, \dots$ across $lo g_{2} n$ levels. $T (n) = Θ (n lo g n)$ .

$a = 4 \Rightarrow r = 2 > 1$ . $T (n) = 4 T (n /2) + O (n)$ . Row work grows geometrically: $n, 2 n, 4 n, \dots$ , dominated by the leaves. Leaf count is $4^{l o g_{2} n} = n^{l o g_{2} 4} = n^{2}$ . $T (n) = Θ (n^{2})$ .

Same $b$ , same $d$ , same tree-building process; only the value of $r$ changed, and the geometric series formula did the rest of the work.

The cheat sheet, now with the reasoning attached

Compare	Ratio	Geometric sum behavior	Dominant term	Total cost
$lo g_{b} a < d$	$r < 1$	bounded by a constant	first term (the root)	$Θ (n^{d})$
$lo g_{b} a = d$	$r = 1$	exactly $k + 1$ equal terms	every level equally	$Θ (n^{d} lo g n)$
$lo g_{b} a > d$	$r > 1$	grows; dominated by $r^{k}$	last term (the leaves)	$Θ (n^{l o g_{b} a})$ , i.e. the leaf count

The "compare $lo g_{b} a$ to $d$ " rule isn't three unrelated facts to memorize. It's one geometric series, the sum of $r^{j}$ , being read in the only three ways a geometric series can behave: shrinking to a constant, staying flat, or exploding toward its final term. And in that last, exploding case, the scary-looking exponent $n^{l o g_{b} a}$ is nothing more than the plain count of leaves at the bottom of the tree. Once that's internalized, no recurrence outside the textbook table needs to be scary again. Draw three rows, work out $r$ , and the geometric sum formula tells you exactly where the weight of the tree sits.

I Didn't "Learn" Sliding Window — I Got Cornered Into It

Amish Singh — Sun, 30 Aug 2026 12:49:16 +0000

The Problem

Given nums list and k operations, where one operation increments one element by 1, find the maximum possible frequency of any value after at most k operations.

Example: nums = [1, 4, 8, 13], k = 5. Best you can do: turn [1, 4] into [4, 4] (cost 3), then you've got 2 operations left over — not enough to reach 8. Answer: 2.

1. Approach 1 — Brute Force

Crux idea: I have k identical operations and N slots (elements). Distribute the k operations among the N slots in every possible way, measure the frequency each distribution gives, keep the best.

def maxFrequency(self, nums, k):
    if k == 0:
        return max(Counter(nums).values())

    m_freq = 0
    for j in range(len(nums)):
        new_list = nums.copy()
        new_list[j] += 1
        m_freq = max(m_freq, self.maxFrequency(new_list, k - 1))

    return m_freq

N choices per operation, k operations → O(N^(k+1)).
nums of length 10, k = 10 → ~10¹⁰ states. Dead on arrival.

The lesson: I was tracking which distribution produced the answer. The problem never asked for that — only the resulting number. Wrong problem, right answer eventually.

2. Approach 2 — Binary Search on the Answer

The thing I actually want is a frequency, and a frequency has a hard range:

low  = max frequency already present in nums
high = len(nums)

For nums = [1, 4, 8, 13]: low = 1, high = 4. Nothing outside [1, 4] is even meaningful.

A number confined to a known range, with a cheap yes/no check → binary search. So the whole problem becomes one boolean predicate:

can(x) = "Can I make x elements equal, using at most k operations?"

Claim: binary search over x is valid.
Property (Monotonicity): can(x) = True ⟹ can(x - 1) = True.
Argument: take any window that hits can(x) at cost C ≤ k. Drop one element from it — same target, less to raise, cost only falls. Still ≤ k. So can(x-1) holds.

Worked example, nums = [1, 4, 8, 13], k = 5:

x	best window	cost	can(x)?
1	any element	0	✅
2	`[1, 4]`, target 4	8 − 5 = 3	✅
3	`[1, 4, 8]`, target 8	24 − 13 = 11	❌
4	`[1, 4, 8, 13]`, target 13	52 − 26 = 26	❌

True, True, False, False — flips once, never back. That's the shape binary search needs: probe the middle, discard a whole half.

3. What `can(x)` Actually Needs

Pick x elements — for what target? I guessed. Took a group, set the target to one of its own values, then nudged the target up and re-checked cost for the same x.

target	window	cost for x=2
4 (in-group)	`[1, 4]`	3
8 (outside group)	`[1, 4] → [8, 8]`	7+4=11
13 (outside group)	`[1, 4] → [13, 13]`	12+9=21

Cost only goes up. Two conclusions:

Target ≥ group's max (can't shrink values).
Target > group's max is pure waste (buys nothing).

So: cheapest target = the group's own maximum. And restricting the target to "one of the elements already in the group" loses nothing — I pick the group, so I pick the target too.

Sort the array, and one more thing falls out for free: the best x elements for a target are never scattered. Here's the detail, with numbers.

4. Why the Best Group Is Always Contiguous

Cost formula for a window [a, b, c] with target c (its own max):

cost = (c-a) + (c-b) + (c-c) = 3*c - (a+b+c)

# general form
cost = target * window_size - window_sum

Let say the input list is [ 1, 2, 4, 5, 7, 9 ]

group	cost = 7×3 − sum
`[2, 5, 7]` (scattered — skips 4, includes 2)	21 − 14 = 7
`[4, 5, 7]` (contiguous — closest 3 to target)	21 − 16 = 5

Contiguous costs less. 2 is farther from 7 than 4 is, so swapping it in wastes budget for nothing.

Claim: for a fixed target, the optimal group of x elements is always contiguous in the sorted array, ending exactly at the target.
Argument: suppose an optimal group skips a larger b for a smaller a, where a ≤ b ≤ target. Swap them. Target unchanged. Cost for that slot drops from target − a to target − b (since b ≥ a) — in the example, swapping 2 for 4 drops that slot's cost from 5 to 3. Repeat for every such gap until none remain → contiguous block, same or lower total cost.

[ 1, 2, 4, 5, 7, 9 ]
        [ 4, 5, 7 ]   ← optimal 3-element group

Not "usually." Always — any gap can be swapped away, so a gapped group was never optimal to begin with.

That still leaves one open question: contiguous ending where? Try the same window [4, 5, 7] against a higher target, 9, instead of 7:

target	cost = target×3 − 16
7 (window's own max)	21 − 16 = 5
9 (higher, forced)	27 − 16 = 11

Cost more than doubles for the same three elements. That's because pushing the target above the window's own max buys nothing — it can't include a bigger element it doesn't have, it just makes every existing element travel further.

Claim: for a fixed contiguous window, the cheapest valid target is its own last (largest) element.
Argument: window [a₁, ..., aₓ], target t ≥ aₓ (can't shrink). Cost:

cost(t) = x·t − Σaᵢ

Linear in t, positive slope → minimized at the smallest feasible t, which is t = aₓ. ∎

BEST WINDOW = contiguous
BEST TARGET = window's last element

5. Why Keep Re-Scanning?

can(x) works: sort, slide a size-x window, check cost. Binary search over x.

It passed. It still bothered me — every new x meant sliding the same window over the same array again, from scratch:

can(3): [1,2,4] [2,4,5] [4,5,7] ...
can(4): [1,2,4,5] [2,4,5,7] ...
can(5): [1,2,4,5,7] ...

"Can't I keep ONE window and just expand or relax it?"

That question is the entire sliding window technique.

6. Approach 3 — One Window That Remembers

Consecutive windows overlap. Don't re-sum from scratch:

new_sum = old_sum - element_leaving + element_entering

Keep state (sum, size, boundaries). Update incrementally. That's the whole trick.

7. Don't Fix the Size Either

if cost <= k:
    # achievable — try to expand
if cost > k:
    # too expensive — relax / move

One pass, no separate scan per x.

8. Why Right to Left?

Largest element = most generous target (everything to its left is a candidate). Start there, narrow only when the budget forces it.

[1, 2, 4, 5, 7]
              ^ target
Everything left of it is candidate space.

9. Two Moves, One Window

Move	Target	Window
`expand_left()`	same	grows by one on the left
`move_left()`	shifts	slides one step left

Every step of the algorithm is one of these two moves. Nothing else happens.

10. The `Window` Class

class Window:
    def __init__(self, nums):
        self.data = nums
        self.ws = len(nums) - 1
        self.we = self.ws
        self.size = 1
        self.window_sum = self.data[self.ws]

    def _update_size(self):
        self.size = self.ws - self.we + 1

    def move_left(self):
        if self.we == 0:
            return False
        self.window_sum = (
            self.window_sum - self.data[self.ws] + self.data[self.we - 1]
        )
        self.ws -= 1
        self.we -= 1
        self._update_size()
        return True

    def expand_left(self):
        if self.we == 0:
            return False
        self.window_sum += self.data[self.we - 1]
        self.we -= 1
        self._update_size()
        return True

    def cost(self):
        return self.data[self.ws] * self.size - self.window_sum

11. The Final Algorithm

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        window = Window(sorted(nums))
        max_freq = 0

        while True:
            if window.cost() > k:
                if not window.move_left():
                    break
            else:
                max_freq = max(max_freq, window.size)
                if not window.expand_left():
                    break

        return max_freq

Too expensive → slide left.
Affordable → record it, try to grow.
Nothing moves → done.

12. What It Costs

Step	Cost
Sort	O(N log N)
Window traversal (each element touched O(1) times)	O(N)
Total	O(N log N)

Started at O(N^(k+1)). That's not a small win.

13. The Whole Chain

graph TD
    subgraph A1["Approach 1 — Brute Force"]
        A1a["Distribute k things among N elements — try every distribution"]
        A1b["Cost: O(N^(k+1))"]
        A1a --> A1b
    end

    A1b --> R1["I care about the resulting frequency, not which distribution produced it."]

    subgraph A2["Approach 2 — Binary Search on the Answer"]
        A2a["Answer has a definite range: [max_freq(nums), len(nums)]"]
        A2b["Ask can(x) instead of enumerating distributions"]
        A2c["Sort the array"]
        A2d["Best group for a target is always contiguous"]
        A2e["Window cost = target × size − sum"]
        A2a --> A2b --> A2c --> A2d --> A2e
    end

    R1 --> A2a
    A2e --> R2["I'm rescanning the same array for every x."]

    subgraph A3["Approach 3 — Sliding Window"]
        A3a["Maintain window_sum + boundaries incrementally"]
        A3b["Let window size grow naturally, no fixed x"]
        A3c["Start from largest target, sweep right to left"]
        A3d["Window class: expand_left / move_left"]
        A3e["Cost: O(N log N)"]
        A3a --> A3b --> A3c --> A3d --> A3e
    end

    R2 --> A3a

    classDef approach fill:#4f46e5,stroke:#4f46e5,color:#fff,rx:6,ry:6;
    classDef insight fill:#fef3c7,stroke:#f59e0b,color:#92400e,rx:6,ry:6;
    class A1a,A1b,A2a,A2b,A2c,A2d,A2e,A3a,A3b,A3c,A3d,A3e approach;
    class R1,R2 insight;

14. What I Actually Learned

Not "spot the pattern, apply sliding window." It was: notice repeated work, refuse to redo it.

Sorted order → optimal group is always contiguous.
Contiguous group → optimal target is always its own last element.

Those two facts turn "maximize a frequency" into "manage a window" — and a window slides.

If you've solved this a different way, or my exchange argument hand-waves somewhere — tell me in the comments.

Incremental Construction with Invariant Checking

Amish Singh — Sat, 29 Aug 2026 10:05:44 +0000

There's a moment in every LeetCode grind where you solve a problem, feel good about it, close the tab, and move on. Then, a day later, the solution taps you on the shoulder and says: you missed something.

That happened to me with Reverse Integer. Twice, actually. And the gap between my first solution and my second isn't really about integers. It's about a decision every one of us makes constantly without noticing: do I figure out the whole plan before I move, or do I move and check my footing with every step?

Let's walk through it.

The Problem, Stripped Down

You're given a signed 32-bit integer x. Reverse its digits. If the reversed number falls outside [-2^31, 2^31 - 1], return 0. Oh, and — twist of the knife — assume you can't just cast to a 64-bit integer to dodge the overflow check. You have to actually reason about the boundary.

That constraint is the whole problem. Reversing digits is trivial. Respecting the 32-bit ceiling without a 64-bit escape hatch is where the thinking happens.

Attempt One: I Went Looking for the Boundary Before I Moved

My instinct was to study the wall before running at it.

I stared at the maximum positive value: 2147483647. And I noticed something almost poetic — the last digit of the original number becomes the first digit of the reversed number. Whatever digit is sitting at the end of x is about to become the leading digit of my answer. That digit alone tells me a lot about whether I'm in danger.

So I built a classification:

If that leading digit is less than 2 — I'm safe no matter what. The biggest possible reversed number starting with 0 or 1 can never beat 2147483647. No further checking needed.
If that leading digit is exactly 2 — now I'm standing right on the edge. This is the case that actually matters. I have to reverse everything after that digit and compare it against 147483647, because that's the only way to know if the full number would tip past the limit.
If that leading digit is greater than 2 — a number starting with 3 through 9 and having 10 digits always overflows. So all I need to check is whether the rest of the number has fewer than 9 digits. If it does, we're fine — the total digit count keeps us under the ceiling regardless of the leading digit.

I want to pause here, because I don't think this deserves the dismissal "overcomplicated" that I initially gave myself in my head. This is a real insight. It's boundary analysis — the same kind of thinking you'd use to prove a mathematical inequality. I looked at the shape of the maximum value, split the problem into cases based on that shape, and pre-validated before doing any actual reversal work.

Here's that solution:

class Solution:

    def reverse_number(self, number):
        is_negative = number < 0
        number = abs(number)

        reversed_number = 0

        while number != 0:
            last_digit = number % 10
            number //= 10

            reversed_number = reversed_number * 10 + last_digit

        return -reversed_number if is_negative else reversed_number

    def get_last_digit(self, number):
        return abs(number - int(number / 10) * 10)

    def get_number_without_last_digit(self, number):
        return int(number / 10)

    def count_digits(self, number):
        number = abs(number)

        if number == 0:
            return 1

        digit_count = 0

        while number != 0:
            number //= 10
            digit_count += 1

        return digit_count

    def is_remaining_number_in_limit(self, number):
        if number < 0:
            return abs(number) <= 147483648

        return number <= 147483647

    def reverse(self, x: int) -> int:
        first_digit_after_reversal = self.get_last_digit(x)
        remaining_number = self.get_number_without_last_digit(x)

        if first_digit_after_reversal < 2:
            return self.reverse_number(x)

        if first_digit_after_reversal == 2:
            remaining_reversed_number = self.reverse_number(
                remaining_number
            )

            if not self.is_remaining_number_in_limit(
                remaining_reversed_number
            ):
                return 0

            return self.reverse_number(x)

        remaining_digit_count = self.count_digits(remaining_number)

        if remaining_digit_count < 9:
            return self.reverse_number(x)

        return 0

It passed. I felt clever. I closed the tab.

The Tap on the Shoulder

The next day, re-reading my own code, something started to itch.

Look at what this solution actually does: it inspects the first digit of the future result before the result exists. It computes remaining_number, fully reverses it in a separate pass, and only then decides if the original reversal is allowed to proceed. It's making a prediction about the outcome of an operation it hasn't performed yet — by partially performing a related operation just to make that prediction.

And that's when the real question surfaced:

Why am I analyzing the whole operation ahead of time — when I'm going to walk through the digits one by one anyway?

I already loop through digits to reverse them. That loop is unavoidable. So instead of doing a pre-flight inspection of where I'll end up, what if I just... checked my footing at each step of the walk itself?

That reframing changed everything. Instead of:

analyze → decide → construct

I could do:

construct → check whether the next step is valid → continue

Attempt Two: Build It, and Ask Permission at Every Step

Here's the idea in plain language. At every iteration of the loop:

Take the next digit off the remaining input.
Before adding it to my partial answer, ask: would appending this digit push my partial answer outside the valid range?
If yes — stop immediately. Return 0. No further work needed.
If no — append the digit.
Shrink the remaining input by one digit.
Repeat.

The key realization is this: I never need to know the final answer to know whether the final answer is illegal. I only need to know whether this specific digit, appended to what I've already built, breaks the rule. If it does, I can bail out on the spot — I don't even need to finish reversing.

This is the invariant at the heart of the whole approach:

The partial reversed_number is always within the valid 32-bit range.

Not "the input is analyzed and therefore the final answer will be in range." Something stricter and more local: at every single point in time during construction, what I currently hold in my hand is legal. I never let an illegal value come into existence, not even for a moment. Before I extend the state, I check whether the extension respects the invariant. If it wouldn't, I simply refuse to take that step.

The overflow check itself becomes almost mechanical once you frame it that way. INT_MAX is 2147483647. If my partial reversed number is already greater than 214748364 (everything except the last digit), then appending any digit will overflow — because that would produce a 10th digit where none is allowed. And if my partial number is exactly 214748364, I only overflow if the new digit is greater than 7 — because 2147483647 is the actual ceiling. The negative side mirrors this with -214748364 and a threshold digit of -8, since the negative floor is -2147483648.

Here's that solution:

class Solution:

    def make_room_for_new_digit(self, number):
        return number * 10

    def append_digit(self, number, digit):
        return self.make_room_for_new_digit(number) + digit

    def get_last_digit(self, number):
        return number - int(number / 10) * 10

    def is_negative(self, number):
        return number < 0

    def would_appending_digit_overflow(self, number, digit):
        if self.is_negative(number):
            return (
                number < -214748364
                or (number == -214748364 and digit < -8)
            )

        return (
            number > 214748364
            or (number == 214748364 and digit > 7)
        )

    def remove_last_digit(self, number):
        return int(number / 10)

    def reverse(self, x: int) -> int:
        reversed_number = 0
        remaining_number = x

        while remaining_number != 0:
            next_digit = self.get_last_digit(remaining_number)

            if self.would_appending_digit_overflow(
                reversed_number, next_digit
            ):
                return 0

            reversed_number = self.append_digit(
                reversed_number, next_digit
            )

            remaining_number = self.remove_last_digit(
                remaining_number
            )

        return reversed_number

No pre-computation of a "remaining reversed number." No separate case for leading digits 0, 1, 2, or 3-through-9. No digit-counting helper. One loop, one check, one invariant. The overflow logic that used to be spread across three branches collapsed into a single guard clause that runs identically on every iteration.

Both solutions are correct. Both pass every test case. But they represent two fundamentally different relationships with the problem — and that difference is the actual article.

The Pattern Underneath: Incremental Construction with Invariant Checking

Here's the thing I want you to take away from this, and it has nothing to do with reversing integers.

My first instinct — and I'd guess it's most people's first instinct — was to scan ahead and decide if the destination is reachable before taking the first step. Figure out the shape of the danger zone, classify where the input falls relative to that zone, then execute.

My second solution replaced that with a different default: take one step, check if that step alone breaks a rule I care about, and only then decide whether to take the next one.

I don't think this pattern has one single, universally agreed-upon textbook name — you'll see pieces of it under "greedy construction," "online algorithms," "streaming validation," or just "short-circuiting." But as a mental model for how I think about these problems now, I call it:

Incremental Construction with Invariant Checking

The shape of it looks like this:

current valid state
       ↓
consider next extension
       ↓
would the extension violate the invariant?
       ↓
   ┌───┴───┐
   no      yes
   ↓        ↓
extend     stop/reject

The state you're building is never allowed to become invalid, not even temporarily. You don't ask "will my final answer be valid?" — a question that usually forces you to either predict the future or do extra work up front to simulate it. You ask a much smaller, much more local question: "does this one next move keep me valid?" And because that question is small, the check is usually cheap, and the logic collapses into something that reads like a single sentence instead of a decision tree.

This shows up everywhere once you start looking for it:

Parsing and validation — instead of scanning a whole string to check if it will end up well-formed, track a running state (like open-bracket depth) and reject the instant a token breaks it.
Streaming systems — you often can't see "the whole input" at all, so you're forced into this pattern: validate each incoming chunk against the current state, and reject or buffer accordingly.
Budget or capacity problems — rather than summing everything first and comparing to a limit, add items one at a time and stop the moment the running total would exceed it.
Building up a data structure under a constraint (a balanced tree, a bounded queue, a rate limiter) — the invariant is the constraint, and every insertion is guarded by "would this insertion break the invariant?" rather than "let me analyze the whole future sequence of insertions."

The underlying lesson is this:

Don't always scan or analyze the entire input to determine whether the final operation is possible.

When a result can be constructed incrementally, consider constructing it step by step — and at each step, ask only whether the next operation would violate the invariant you're protecting.

It's a smaller question, asked more often, instead of one big question asked once. And smaller questions, asked at the right moment, tend to produce simpler code.

Why I'm Glad I Didn't Stop at the First Solution

If I'd stopped after my first pass, I would have walked away with a working answer to a LeetCode problem. Nothing wrong with that — it was a legitimate insight, and I stand by the boundary-case reasoning behind it.

But sitting with the discomfort of "this feels like more machinery than it should need" is what surfaced the actual transferable skill. The second solution isn't better because it's shorter. It's better because it changed the question I was asking the problem. I stopped asking "what will happen if I do this?" and started asking "is it still safe to do this, right now, given where I already am?"

That's a question worth carrying into the next problem — whichever one it happens to be.

Concentric Square Ring Pattern: Peeling the Onion on Two Ways I Accidentally Solved It

Amish Singh — Sat, 29 Aug 2026 06:12:39 +0000

Concentric Square Ring Pattern: Peeling the Onion on Two Ways I Accidentally Solved It

There's this pattern problem that looks harmless until you actually sit down and try to generate it:

5 5 5 5 5 5 5 5 5
5 4 4 4 4 4 4 4 5
5 4 3 3 3 3 3 4 5
5 4 3 2 2 2 3 4 5
5 4 3 2 1 2 3 4 5
5 4 3 2 2 2 3 4 5
5 4 3 3 3 3 3 4 5
5 4 4 4 4 4 4 4 5
5 5 5 5 5 5 5 5 5

Concentric squares. A 1 locked in the center, growing outward ring by ring to n at the border. Simple to look at. Deceptively slippery to generate.

I want to walk through this the honest way — not the clean, confident version you write after you already know the answer, but the actual sequence of wrong turns, half-formed guesses, and the two genuinely different mental models I ended up building before it clicked. Think of it as peeling an onion: each layer looked like the final answer until I dug one level deeper and found another shape underneath.

Layer One: "It's Just Rows"

My first foothold wasn't the grid. It was a single row.

I looked at the exact middle row — the one slicing straight through the center — and read it like a sentence:

5 4 3 2 1 2 3 4 5

A lonely 1 in the center. Then 2 on both sides of it. Then 3. Then 4. Growing outward, symmetrically, until it caps out at n on both ends.

Okay, I thought, that's just a palindrome that counts down to the middle and back up. Nothing scary about a single row.

So I moved up one row:

5 4 3 2 2 2 3 4 5

Same shape — but now the smallest number, 2, isn't alone anymore. It's repeated three times in the middle. One row further up:

5 4 3 3 3 3 3 4 5

Now 3 is repeated five times.

That's when the pattern behind the pattern showed up: every row is a number, repeated some number of times, sandwiched on both sides by every number bigger than it, counting up to n.

Row (top → center)	Center value	Repeated	Sandwich
edge row	`5`	9 times	nothing bigger — it is the ceiling
next in	`4`	7 times	`5`
next in	`3`	5 times	`4, 5`
next in	`2`	3 times	`3, 4, 5`
center row	`1`	1 time	`2, 3, 4, 5`

I had a rule I could actually build. For the i-th row down from the top (0-indexed), the center value is n - i, and it needs to be sandwiched by everything from n-i+1 up to n. So the row is: count down to the center value, place the center value repeated enough times to fill the middle, count back up.

row = list(range(n, n-i, -1)) + [n-i]*(2*(n-i)-1) + list(range(n-i+1, n+1))

range(n, n-i, -1) → the left sandwich: counting down from n to just above the center value
[n-i]*(2*(n-i)-1) → the center value, repeated exactly enough to fill the row's width at that depth
range(n-i+1, n+1) → the right sandwich: counting back up to n

Build that for every row from the top down to the center, and you've got the top half of the grid:

def pattern(n):
    N = 2 * n - 1
    upper = []
    for i in range(n):
        row = (list(range(n, n-i, -1))
               + [n-i] * (2*(n-i)-1)
               + list(range(n-i+1, n+1)))
        upper.append(row)

    for i in range(n):
        print(*upper[i])

    for i in range(1, n):
        print(*upper[n-i-1])

And here's the part that felt like a small gift: the bottom half of the grid is the same rows, in reverse. I don't need to derive it separately — I already built it once going down. So the second loop just walks back up through upper, skipping the center row so it isn't printed twice.

At this point I was satisfied. I had working code. I understood every line. Case closed... except it wasn't, because a nagging question kept surfacing: I built this entirely in terms of rows and horizontal sandwiches — but this is supposed to be a square. Where did the "squareness" actually go into the logic? The answer was: nowhere, directly. It fell out as a side effect of the row math. That bugged me enough to keep going.

Layer Two: "Wait, It's Actually Rings"

The row-sandwich model works, but it treats the grid as a stack of independent horizontal problems. To see the actual shape underneath it, I have to back up to where this really started — because before I ever wrote a sandwich formula, my first instinct was something else entirely.

My first instinct was to think of it as a circular pattern — a ring radiating out from the center. That felt intuitive: each cell's value should just be its distance from the center.

So I tried to apply that. For any cell, I know its (x, y) position and I know where the center is — easy, right? But then it broke down immediately: distance to the center isn't uniform across a square. A cell on the edge, straight out from the center, is at one distance. A cell on the diagonal, same "ring," is at √2 times that distance. The shape I wanted was a square ring, not a circle, so "distance from center" was the wrong metric from the start — it doesn't produce flat, even rings, it produces actual circles.

That's when I reframed it: forget distance from the center — think of it as ring numbers, counting outward. The innermost ring — just the single center cell — is ring 1. The ring just outside it is ring 2, and so on, growing outward until the very last ring, ring n, is the outer boundary of the whole square.

To actually convince myself of this, I sketched it out:

I drew the outer square, and then looked at the space just inside it — the next ring in. And there it was: a corner cell of that ring and an edge-mid cell of that same ring — one sitting on the diagonal, one not — were exactly the same distance from the boundary. Not wider at the corner, not narrower along the edge. One consistent gap, wrapping the whole boundary evenly, whether you measured it from a diagonal position or not.

That consistent gap was the click. If that space is always uniform, then I don't need to think about rings as some abstract counting exercise — I can just measure it. Given the size of the whole grid, finding how far in a cell sits from the boundary is a simple calculation. And since that distance is measured from the outside in, while ring numbers grow from the inside out, the two are just mirror images of each other: the ring number is that distance, reversed — n minus however far the cell is from the edge.

That was the real unlock: the value of a cell isn't about its distance to a point, it's about its distance to a boundary — and once I could measure that distance, the whole formula fell out of it.

For a cell at (i, j) in an N × N grid, its distance from the boundary is simply the smallest of its distances to all four sides:

distance_from_left   = j
distance_from_top    = i
distance_from_right  = N - 1 - j
distance_from_bottom = N - 1 - i

distance_from_edge = min(distance_from_left, distance_from_top,
                          distance_from_right, distance_from_bottom)

A corner cell is 0 distance from two edges simultaneously — no √2 involved, because we're not measuring toward a single point anymore, just toward whichever side is nearest. That single change is what makes the rings come out square instead of circular.

The last step was just relabeling that distance as a ring value. Distance-from-edge counts inward — 0 at the boundary, growing as you approach the center. Ring numbers, at least the way I'd been drawing them, count the opposite way — 1 at the center, growing as you go outward. They're mirror images of the same measurement, so:

ring_value = n - distance_from_edge

def pattern(n):
    N = 2 * n - 1
    for i in range(N):
        row = []
        for j in range(N):
            distance_from_edge = min(i, j, N-1-i, N-1-j)
            row.append(n - distance_from_edge)
        print(*row)

No rows-as-sandwiches, no upper/lower split, no reversed lists. Every cell computes its own value, independently, from one idea: how close am I to getting out of this square?

The Two Layers, Side by Side

	Row-Sandwich Model	Ring-Distance Model
Unit of thought	one row at a time	one cell at a time
Core question	"what number, repeated how many times, sandwiched by what?"	"how far am I from the nearest edge?"
Where symmetry lives	reuse rows top-to-bottom	built-in — every direction is checked equally
What broke my first guess	— (this was the first working model)	distance-to-center makes circles, not squares
Feels like	counting outward from the middle of a line	shrinking inward from the walls of a box

Neither one is "more correct" than the other — they're two honest descriptions of the same object, discovered in a different order, through different mistakes. The row model came from staring at a line. The ring model came from staring at my own bad drawing and noticing a gap that refused to change width. Both times, the wrong first guess — a lonely row with no shape, a distance measured to a point instead of a wall — was doing useful work. It's what made the eventual correction mean something instead of just being a formula I copied from somewhere.

That, more than the code itself, is the part worth remembering: the formula is three lines. Getting to the point where it feels obvious takes a wrong turn or two on purpose.

The Docker Layer Duplication Penalty: Why Modifying Files in Old Layers Costs You Twice

Amish Singh — Sat, 22 Aug 2026 16:14:02 +0000

As modern backend developers, we all know the drill: Never run your containers as root. It's a massive security hazard.

To fix this, the intuitive workflow most of us learn is straightforward:

Copy your application code and virtual environments into the container as root.
Create a restricted, non-root system user profile.
Run a swift RUN chown -R appuser:appuser /app right at the bottom to hand over permissions.

It builds successfully. The app runs. You push it to production. Job well done, right?

Wrong. You just triggered a silent architectural tax known as the Layer Duplication Penalty.

Let's look at a live terminal discovery that catches Docker's layering engine red-handed, and see how trying to fix user permissions can either double your image size or silently brick your application.

The Accidental Discovery

While debugging a Python 3.13 production multi-stage build, I decided to pull back the sheets on the container layers using docker history. I built two different variations of the image: n-py (the standard layered approach) and m-py (a selective path "optimization" attempt).

Take a close look at the layer footprint from docker history n-py:latest:

IMAGE          CREATED         CREATED BY                                      SIZE
<missing>      3 minutes ago   COPY --chown=appuser:appuser . .                28.7kB
<missing>      3 minutes ago   COPY --chown=appuser:appuser /opt/venv /opt/…   91.7MB
<missing>      3 minutes ago   RUN /bin/sh -c chown -R appuser:appuser /opt…   91.7MB

Look at that double-take payload!

COPY /opt/venv enters the ring at 91.7MB (originally owned by root).
RUN chown -R appuser:appuser /opt/venv registers another 91.7MB right above it.

Because we ran a separate RUN chown command on a directory that was already frozen in a previous layer, Docker duplicated all 91.7MB of dependencies a second time just to alter the user metadata.

The Hazard "Optimization" Trap

Seeing this bloat, your immediate engineering instinct might be: "Fine, I'll just narrow the chown to my local app directory in the home folder, and leave the virtual environment alone — it's a system path anyway." It's a reasonable guess. It's also wrong, and it's worth walking through exactly why, because the failure mode it produces is worse than the bloat you started with.

That instinct creates image m-py:

IMAGE          CREATED         CREATED BY                                      SIZE
<missing>      4 minutes ago   COPY . .                                        28.7kB
<missing>      4 minutes ago   COPY /opt/venv /opt/venv                        91.7MB
<missing>      4 minutes ago   RUN /bin/sh -c chown -R appuser:appuser /hom…   28.7kB

The manual chown layer dropped from 91.7MB down to a microscopic 28.7kB. We bypassed the duplication penalty.

But there's a catch: because /opt/venv sits at the system root level (/opt/), the narrowed chown path never touches it. The 91.7MB virtual environment is still 100% owned by root. The moment the container switches to USER appuser and boots up, Python drops dead with a fatal PermissionError: [Errno 13] Permission denied, because a low-privilege user is trying to execute locked-down dependencies.

You're stuck with a brutal choice: double your image footprint, or silently brick your runtime.

Deep Dive: Why Modifications Pay a 100% Tax

To understand why Docker behaves this way, look at the Union File System (UnionFS). Docker images are stacked like immutable sheets of glass. Once a layer is built and sealed, it is permanent and read-only.

In Linux, file permissions and ownership (UID/GID) aren't separate config floating around — they're metadata baked directly into the filesystem blocks of the files themselves.

When you execute a RUN chown in a subsequent layer, Docker can't travel back in time to edit Layer 1. Instead, it triggers a Copy-on-Write (CoW) event:

Docker copies the files up from the frozen layer into the active layer.
It rewrites the filesystem metadata tags to match your new non-root user.
It uses a virtual filesystem overlay to hide the original root files underneath.

To your terminal, it looks like a clean modification. To your deployment bandwidth and disk space, the data now exists twice.

This is the same reason multi-stage builds help elsewhere but don't save you here on their own: a multi-stage build lets you drop an entire build stage's layers from the final image, but it doesn't make a layer's own contents editable once sealed. If you COPY as root in your final stage and chown afterward in that same stage, you pay the tax regardless of how clean your earlier stages are.

A quick note on why this doesn't apply to folders the same way it applies to files: in most Linux filesystems, a directory isn't a physical container of data — it's closer to a small index of names and pointers to where the actual data blocks live.

Adding a new file to an existing folder only requires a tiny record in the new layer.
Modifying an existing file's metadata — including ownership — costs 100% of that file's size, because the file's data blocks get copied up whole.

The Clean Solution: Inline Interception

You don't need to choose between bloat and instability. Intercept the permissions at the exact moment the data enters the container layer — BuildKit's inline --chown flag on COPY stamps files with the right ownership as they're written, so there's no separate modification layer to pay for.

A Fuller Before-and-After

The toy example above proves the mechanism, but real Dockerfiles have more going on — pinned base images, pip flags, hash-randomization settings. Here's the antipattern at full scale, the way it actually shows up in a production build:

# ❌ BEFORE — pays the duplication tax twice
FROM python:3.13-slim@sha256:ffb752e139c0a19692a43af8d8523b274222dd68eebad5d583b45c2201c6e30a AS builder
WORKDIR /build

ENV PIP_NO_CACHE_DIR=1 \
    PIP_DISABLE_PIP_VERSION_CHECK=1

RUN python3 -m venv /opt/venv
COPY requirements.txt .
RUN /opt/venv/bin/pip install -r requirements.txt


FROM python:3.13-slim@sha256:ffb752e139c0a19692a43af8d8523b274222dd68eebad5d583b45c2201c6e30a
WORKDIR /home/appuser/app

ENV PYTHONUNBUFFERED=1 \
    PYTHONFAULTHANDLER=1 \
    PYTHONHASHSEED=random \
    PATH="/opt/venv/bin:$PATH"

RUN useradd -U -m -s /bin/bash appuser

# Copied as root, with no ownership stamp — the tax gets paid later
COPY --from=builder /opt/venv /opt/venv
COPY . .

# Two RUN chown calls, each rewriting a frozen layer's files:
RUN chown -R appuser:appuser /home/appuser/app
RUN chown -R appuser:appuser /opt/venv

USER appuser
CMD ["python3", "main.py"]

That second pattern is worth calling out on its own: two separate RUN chown instructions, each one walking back over data that a previous COPY already froze into a layer. Every path you list there — the app directory and the venv — pays the full CoW tax independently. It's the same mistake as the single-chown case earlier, just spread across two commands instead of one, which makes it easy to miss in a longer Dockerfile. (Worth noting too: a bare RUN chown -R appuser:appuser with no target path isn't just wasteful, it's an invalid command — chown needs an operand to act on, and Docker will fail the build outright rather than silently doing nothing.)

Here's the same build with the tax removed:

# ✅ AFTER — ownership is stamped inline, nothing gets rewritten
FROM python:3.13-slim@sha256:ffb752e139c0a19692a43af8d8523b274222dd68eebad5d583b45c2201c6e30a AS builder
WORKDIR /build

ENV PIP_NO_CACHE_DIR=1 \
    PIP_DISABLE_PIP_VERSION_CHECK=1

RUN python3 -m venv /opt/venv
COPY requirements.txt .
RUN /opt/venv/bin/pip install -r requirements.txt


FROM python:3.13-slim@sha256:ffb752e139c0a19692a43af8d8523b274222dd68eebad5d583b45c2201c6e30a
WORKDIR /home/appuser/app

ENV PYTHONUNBUFFERED=1 \
    PYTHONFAULTHANDLER=1 \
    PYTHONHASHSEED=random \
    PATH="/opt/venv/bin:$PATH"

RUN useradd -U -m -s /bin/bash appuser

# Ownership is set as the bytes land — no separate RUN, no CoW event
COPY --from=builder --chown=appuser:appuser /opt/venv /opt/venv
COPY --chown=appuser:appuser . .

USER appuser
CMD ["python3", "main.py"]

Same base image, same pinned digest, same env vars — the only difference is where the ownership gets assigned. docker history on the "after" build shows no RUN chown line at all, because there's nothing left for it to do.

The Production Payoff

Check the history of the inline layout and the duplicate layer vanishes entirely. The virtual environment lands exactly once, already owned by appuser.

Because your non-root worker has native ownership over its /home workspace, Python can generate performance-boosting .pyc caches at runtime without hitting a permissions wall.

The Golden Rule of Layers

Docker layers are strictly cumulative, never subtractive or editable.

Additions are close to free.
Modifications — including ownership changes — pay a tax proportional to what they touch.

Run docker history <image_name> on your own images tonight. If you see redundant size payloads mirroring your COPY steps, swap them out for inline --chown flags. Your deployment pipeline, cloud bill, and cold-start times will thank you.

My Docker Build Was Slow Before It Even Started, Here's Why

Amish Singh — Thu, 20 Aug 2026 17:37:11 +0000

We build several independently deployed Python API services out of one monorepo — an image-processing service, a document service, a similarity service, and a handful of others. They all share a common/ package with GCP storage helpers, parallel download utilities, and other plumbing nobody wants to duplicate three times.

One afternoon I ran a build for image-service and watched this happen:

[internal] load build context
=> transferring context: 1.48GB

Ten seconds. Before a single line of the Dockerfile had executed. Ten seconds just to hand files to the builder.

That line is what sent me down the rabbit hole this post is about.

The Setup

Here's roughly what the repo looks like:

repository/
├── common/
│   ├── gcp/
│   │   ├── download.py
│   │   ├── upload.py
│   │   └── storage.py
│   └── utils/
│
├── services/
│   ├── image-service/
│   │   ├── Dockerfile
│   │   ├── src/
│   │   └── models/
│   │       └── model.bin        # ~1.5GB
│   │
│   ├── document-service/
│   │   ├── Dockerfile
│   │   └── src/
│   │
│   └── similarity-service/
│       ├── Dockerfile
│       └── src/
└── ...

image-service ships with a local ML model file baked into the repo (don't ask — legacy reasons). It needs two things to build: its own source, and common/. Simple enough, except those two requirements pull in opposite directions on how you'd normally structure a build.

Attempt 1: Repo Root as Context

The obvious move, since common/ lives at the top level, is to build from the repo root:

docker build -f services/image-service/Dockerfile .

This works. The Dockerfile can do COPY common/ /app/common because everything under the repo root — including common/, every other service, every model file, every .git object — is now part of the build context: the set of files the Docker client tars up and streams to the builder before a single instruction runs.

That's the part that tripped me up initially. I assumed context size and image size were basically the same problem. They aren't.

Build context is what gets sent to the daemon/builder as raw input. Image size is what actually ends up in the layers of the final image, after your Dockerfile's COPY/ADD/RUN instructions decide what to keep. You can have a 1.5GB context and a 200MB image, because the model file for document-service never gets copied into image-service's image at all — it's just sitting there, transferred over the wire, unpacked, and then ignored.

That transfer isn't free. Every docker build from repo root re-sends the entire context — including every other service's model files, .git history, virtualenvs, whatever — even though image-service only needs a fraction of it. That's where the 10-second, 1.48GB "transferring context" step came from. Not a slow build. A build that hadn't even started yet.

Attempt 2: Shrink the Context

So the next instinct: build from inside the service directory instead.

cd services/image-service
docker build .

Now the context is just image-service/ — no other services, no unrelated model files, no repo-wide .git. Fast, small, focused.

Except now common/ is gone. It's outside the build context entirely, and the Dockerfile has no way to reach it:

COPY ../../common /app/common

This fails, and it's worth understanding why rather than just memorizing "don't do that." A build context isn't just "the current directory" in some loose sense — it's a boundary. The Docker client only ever tars up and sends what's inside the context you pointed it at. Instructions inside the Dockerfile can't reach outside that boundary using ../ or any other path trick, because as far as the builder is concerned, nothing outside the context exists. It was never transferred. There's nothing to COPY from.

So we're stuck between two bad options:

Repo root as context → everything's reachable, but the context is huge and mostly irrelevant to any single build.
Service directory as context → fast and focused, but common/ is unreachable.

Attempt 3: The Temporary Directory Hack

The first real fix I reached for was filesystem manipulation. Stage a temporary directory that contains exactly what the build needs, and build from there:

/tmp/image-service-build/
├── Dockerfile
├── src/
├── models/
└── common/

A small shell script does the assembly:

#!/usr/bin/env bash
set -euo pipefail

BUILD_DIR=$(mktemp -d)

cp -r services/image-service/* "$BUILD_DIR/"
cp -r common "$BUILD_DIR/common"

docker build -t image-service -f "$BUILD_DIR/Dockerfile" "$BUILD_DIR"

rm -rf "$BUILD_DIR"

This works, and for a while it was our actual solution. But it bothered me. We were solving a build-input problem — "this build legitimately needs files from two different locations" — by physically rearranging the filesystem to fake a single location. It's copy-paste as architecture. Every service needs its own version of this script, and any deviation between the service's actual layout and what the script assembles becomes a silent, easy-to-miss bug.

There had to be a way to tell Docker directly: "the build needs inputs from two places," without lying to it about where those places are.

Attempt 4: Named Build Contexts

This is what BuildKit's named build contexts are for. Instead of forcing everything into one directory, you give the builder multiple, independently named sources for a single build:

docker build \
  --build-context common=./common \
  -f services/image-service/Dockerfile \
  services/image-service

Breaking this down:

services/image-service (the final positional argument) is the default build context — this is what unqualified COPY instructions read from.
--build-context common=./common registers an additional, named context called common, pointing at the common/ directory.
Nothing gets merged or copied on disk. Both contexts stay exactly where they are; the builder just knows about both of them now.

The Dockerfile then references each context explicitly:

FROM python:3.12-slim

WORKDIR /app

# reads from the default context: services/image-service/
COPY . /app

# reads from the named context: "common"
COPY --from=common . /app/common

RUN pip install --no-cache-dir -r requirements.txt

CMD ["python", "src/main.py"]

The key line is COPY --from=common . /app/common. Normally --from in a COPY refers to a previous build stage in a multi-stage build. With named build contexts, --from can also refer to a named context registered via --build-context. So this instruction means: "copy everything from the common context (i.e. ./common on disk) into /app/common in the image" — completely independent of whatever the default context is doing.

Conceptually, the build now looks like this:

Docker Build
├── default context
│   └── services/image-service/
│       ├── Dockerfile
│       ├── src/
│       └── models/
│
└── named context: common
    └── common/
        ├── gcp/
        └── utils/

Two separate, explicit inputs. No repo-root scan. No temp directory. No ../../ path traversal that the builder would reject anyway.

This is strictly better than the repo-root approach because the build now only ever sees what it actually asked for. document-service's model file, similarity-service's source, the .git directory — none of it is transferred, none of it is even considered, because it was never part of either context.

.dockerignore: Also About Context, Not Just Image Size

It's easy to think of .dockerignore as "the file that keeps junk out of my image." That's a side effect, not the main point. .dockerignore controls what enters the build context in the first place — before the Dockerfile ever runs, before any COPY decides what to keep.

A typical one for a service like this:

.git
__pycache__
.venv
*.log
tests/

The flow looks like:

Repository
    ↓
.dockerignore   (filters what gets read into the context)
    ↓
Build context   (what's actually sent to the builder)
    ↓
Dockerfile      (decides what from the context becomes image layers)
    ↓
Image

One thing worth being precise about: .dockerignore applies to the context it lives next to — it doesn't automatically reach across and filter every named context you register separately. If you have a .dockerignore in services/image-service/, it governs the default context (services/image-service/). It has no bearing on what gets sent from the common named context unless common/ has its own .dockerignore. Named contexts and .dockerignore solve two different questions:

.dockerignore answers: what files should be excluded from this context?
Named build contexts answer: what additional, explicitly named sources should this build consume at all?

One trims an input you already have. The other declares an input you didn't have before. They're complementary, not substitutes for each other.

The Insight That Actually Mattered

The deeper realization here wasn't really about Docker flags. It was this:

The repository structure and the build structure don't have to be identical.

The monorepo is organized the way developers want to navigate it:

repository/
├── common/
├── service-a/
├── service-b/
└── service-c/

But a given Docker build shouldn't default to "the repository" just because the Dockerfile happens to live somewhere inside it. A build should be scoped to its actual inputs:

image-service/
    +
common/

not

entire repository

This matters more as a monorepo accumulates the things monorepos tend to accumulate: multiple independently deployable services, shared libraries, ML models, generated files, frontend and backend projects living side by side, node_modules, datasets, test artifacts, documentation. None of that is relevant to any single service's build, and none of it should be treated as if it were just because it's reachable from the repo root.

What I Got Wrong Initially

A few assumptions I had to unlearn:

I thought the Dockerfile's location determined the build context. It doesn't — the context is whatever path (or paths) you point docker build at; the Dockerfile can live anywhere and be referenced with -f.
I treated "the repository" as the natural, default build context for anything inside a monorepo, mostly out of convenience.
I assumed a large context mainly mattered because it would produce a larger final image. It doesn't directly — context size and image size are separate concerns, linked only by what your COPY instructions choose to keep.
I saw the temp-directory copy trick as the only real workaround for cross-directory dependencies, because I didn't yet know named build contexts existed as a first-class BuildKit feature.

The Mental Model I Use Now

Before writing or changing a Dockerfile in this repo, I ask three questions:

What is my build context? Where am I telling docker build to look, and what does that actually include?
What are the actual inputs required by this build? Not "what's nearby," but what does this specific service genuinely need to compile and run?
Which files are unnecessary and should be excluded? Anything not required is a candidate for .dockerignore or for simply not being in the context in the first place.

In practice that translates to:

Default to a focused, service-scoped build context — not the repo root.
Use .dockerignore to keep incidental junk (caches, logs, test artifacts, VCS metadata) out of whatever context you do use.
Reach for named build contexts when a build legitimately needs files that live outside its natural directory — shared libraries, generated schemas, whatever.
Don't reach for repo-root-as-context just because it's the path of least resistance in a monorepo.

Final Picture

MONOREPO
│
├── common/
│
├── services/
│   ├── image-service/
│   ├── document-service/
│   └── similarity-service/
│
└── ...

For image-service specifically, the build only ever sees:

Docker Build
├── default context
│   └── image-service/
│
└── named context: common
    └── common/

Nothing else in the monorepo is transferred, scanned, or even visible to this build.

Key Takeaways

Build context size and final image size are different things — a huge context doesn't necessarily mean a huge image, but it does mean slower, wasteful transfers.
A Dockerfile can't reach outside its build context with ../ — the context is a hard boundary, not just "the current directory."
Named build contexts (--build-context name=path + COPY --from=name) let a single build pull from multiple, explicitly declared locations without merging anything on disk.
Temporary-directory staging scripts work, but they're a filesystem workaround for what's really a build-configuration problem.
.dockerignore filters its own context — it doesn't automatically apply to separately named contexts.
In a monorepo, the build context should represent the service's actual inputs, not the repository's overall layout.
Don't make your repository the build context by default. Make the build context represent the actual inputs required by the build.

The Recursive Mindset: Unlocking the Code You Already Know

Amish Singh — Thu, 21 May 2026 17:09:38 +0000

The Philosophy: Why This Article Exists

You might have opened a computer science textbook or scrolled through tutorials and hit a wall.

There are two traps that people fall into:

The Overly Academic Trap: Some platforms make concepts sound scary with formulas and jargon that leaves your questions unanswered.
The Hyper-Focused Scope Trap: Some tutorials teach you how to copy-paste code. Don't teach you how to think like a problem solver.

I wanted to change that. I think to master an algorithm you need to see how it relates to real life.

I am not going to oversimplify things.

My goal is to balance accuracy with engaging storytelling. I want anyone to be able to read this enjoy it and understand how things work.

When I tackle concepts I turn them into stories. Like a conversation between a Guide and a Learner in a coffee shop figuring things out from scratch. Code is details; the intuition is where the magic happens.

Welcome to a way of learning. Lets learn how to chew.

This series is my solution. Every time I tackle a technical concept I strip away the academic pretension and transform it into a story—a conversation between a Guide and a Learner sitting in a coffee shop figuring things out from scratch. Because code is the paperwork; the intuition is where the magic happens.

Welcome to a way of learning. Lets learn how to chew.

The Setup

The coffee shop is buzzing with the hum of espresso machines and light chatter. At a corner table sunlight streams across two filled notebooks, a couple of coffees and a single laptop open to a blank text editor.

There is no panic the quiet casual energy of two people hanging out ready to build something cool from scratch. The Guide takes a sip of their drink looks at the screen and smiles at the Learner.

Guide: You know there is something satisfying about a blank file. It is like a notebook. No bugs no logic. Just pure potential. How are you feeling about diving into the project today?

Learner: Honestly? I am excited. Of amused. I was looking at the syllabus for what we need to implement. The first topic is titled "The Divide and Conquer Paradigm." It sounds like programming and more like an emperor trying to take over Europe. I am just wondering why computer science loves making simple things sound so intensely academic.

Guide: The Guide laughs. You are not wrong. Academic textbooks have a talent for making intuitive ideas look like terrifying ancient runes.. What if I told you that you have been using the Divide and Conquer paradigm since you were a kid? You are actually already a master at the Divide and Conquer paradigm.

Learner: That is a claim. I am pretty sure I have not conquered any empires recently.

Guide: Maybe not empires,. Let us talk about street food. Imagine you and your sister walk up to your Pani Puri stall. You look at the bhaiya. Say, "Bhaiya, plate challenge. Give us 60 golgappas now."

Learner: The Learner laughs. Okay first of all if I try to shove 60 golgappas into my mouth at the time I will literally choke and explode.

Guide: Exactly. You physically cannot solve the "60 Golgappas" problem at once. The human brain.. Stomach. Short-circuits at that scale. So what actually happens? How do you and your sister eat the Divide and Conquer paradigm golgappas?

Learner: Well obviously we split the problem in at the start. I tell the bhaiya "Put 30 on her plate and 30 on my plate."

Guide: Boom. Step one done. You took a 60-unit problem. Split it into two identical 30-unit problems.. Wait can you eat 30 golgappas in one gulp?

Learner: No. I am a human, not a hole. Even the 30 on my plate is too big to handle in one go. So I ignore my sisters plate look at my 30 and the bhaiya starts serving them to me one by one. I take one golgappa crunch it swallow it and repeat.

Guide: Pause. Look at the magic of what happened.

You had a problem: Eat 60 Golgappas.

You split it into two problems: Eat 30 Golgappas.

How do you solve the 30? By breaking it down until you are dealing with the smallest most trivial version of the problem: Eat 1 Golgappa.

Can you eat 1 golgappa?

Learner: Easily. It is a bite.

Guide: Exactly. That single bite is what we call the Base Case in computer science. It is a problem you do not need to break it down anymore; you just solve it instantly.

Now what happens when you finish eating your 30 golgappas and your sister finishes eating her 30 golgappas?

Learner: The bhaiya wipes the counter counts the small bowls adds our two plates together and says, "Sahab, 60 ho gaye." The giant 60-golgappa problem is completely solved.

Guide: Look at what you did. You did not need a professor to teach you the Divide and Conquer paradigm. Your hunger naturally figured out the algorithm template in history. You followed a three-step ritual:

Divide: You took a problem. The Divide and Conquer paradigm.. Split it into two identical smaller versions of the same problem.
Conquer: You solved the problems by breaking them down all the way to the possible unit, which you can solve effortlessly.
Combine: You let the results of those bites gather up until the entire original mountain of food was gone.

In Computer Science we just call this the Divide and Conquer paradigm.

Learner: Wait. Seriously? So the Divide and Conquer paradigm is not a formula? It is literally just... Breaking a problem down into versions of itself until it is small enough to handle in one bite?

Guide: That is the rule. The sub-problems must be mirrors of the problem. Eating a golgappa is a version of eating a plate of golgappas.

When we write code like Merge Sort to sort a million numbers the computer does not try to sort all million at once. It panics, just like you did at the number 60. So it splits the million numbers in half. Then it splits those halves in half. It keeps splitting until it is looking at one number.. Sorting a number is as easy as eating a single golgappa. It is already done. Then it just merges them up.

Learner: Wow. Okay seeing it like that actually takes all the anxiety away. I have been executing algorithms every time I eat on the street. So of staring at a file wondering how to write a massive complex system I just need to ask myself: "What is the single-bite version of this problem?"

Guide: Precisely. You already have the intuition; we just need to teach your keyboard how to chew.

The Wrap-Up

Learner: Wait, no way. Look outside the sun is already setting. How did we spend three hours talking about pani puri?

Guide: Time flies when you are realizing you are smarter than the textbooks give you credit for.

Learner: Honestly I am glad we did not touch the keyboard yet. My brain feels full. In a way. For once I am actually looking forward to opening this file tomorrow.

Guide: You know there is a reason I wanted to start with this today. It is not, about passing your exams or writing efficient code.

Learner: What do you mean?

Guide: Think about it. When you looked at the syllabus earlier you felt that sudden weight of anxiety right? The "60 golgappas" of a curriculum. Life does that to us all the time. It throws a chaotic problem at your feet. A huge project, a relationship choice or a massive career decision.. Your brain panics. It freezes because it tries to swallow the 60-unit problem at once.

Learner: Yeah... That is what burnout feels like. Just staring at a mountain. Feeling paralyzed.

Guide: You know computer science isn't that complicated. It's actually pretty simple. Algorithms are a way to live your life. When things get really crazy you don't have to try to fix everything at. Just look at the mess find a way to make it smaller and ask yourself "What's one thing I can do now to make it better?"

The Living Algorithm

You don't fix your life at once. You start with one thing. You clear off one desk. You send one email. You take one breath. You deal with one thing in front of you trust that it will all work out and let the small wins add up over time. Don't be scared of a problem. If a computer can take a billion pieces of information and make sense of them you can take any problem. Break it down into one small step.

Learner: I never thought about it that way. I mean I've always thought of computer science as code but it actually makes sense for life too. What's the one thing I can do now to make this problem better?... Yeah I really needed to hear that.

Guide: . Grabs his backpack. I love it when people get it. When you look at things differently everything seems easier. Lets go the cafe is closing. I have my phone with me lets find a spot and play that game we've been putting off.

To be continued....

DEV Community: Amish Singh

The Master Method and it's Intuition

Step 1: Build the tree, one level at a time

Step 2: The general formula for row j

Step 3: Total work is a geometric series

Case 1: r is less than 1, the sum is bounded by a constant and dominated by the first term

Case 2: r equals 1, every term is equal and the sum is just the level count

Case 3: r is greater than 1, the sum is dominated by the last term

Why that exponent is exactly the leaf count

Worked example: fixing b and d, varying only a

The cheat sheet, now with the reasoning attached

I Didn't "Learn" Sliding Window — I Got Cornered Into It

The Problem

1. Approach 1 — Brute Force

2. Approach 2 — Binary Search on the Answer

3. What can(x) Actually Needs

4. Why the Best Group Is Always Contiguous

5. Why Keep Re-Scanning?

6. Approach 3 — One Window That Remembers

7. Don't Fix the Size Either

8. Why Right to Left?

9. Two Moves, One Window

10. The Window Class

11. The Final Algorithm

12. What It Costs

13. The Whole Chain

14. What I Actually Learned

Incremental Construction with Invariant Checking

The Problem, Stripped Down

Attempt One: I Went Looking for the Boundary Before I Moved

The Tap on the Shoulder

Attempt Two: Build It, and Ask Permission at Every Step

The Pattern Underneath: Incremental Construction with Invariant Checking

Why I'm Glad I Didn't Stop at the First Solution

Concentric Square Ring Pattern: Peeling the Onion on Two Ways I Accidentally Solved It

Concentric Square Ring Pattern: Peeling the Onion on Two Ways I Accidentally Solved It

Layer One: "It's Just Rows"

Layer Two: "Wait, It's Actually Rings"

The Two Layers, Side by Side

The Docker Layer Duplication Penalty: Why Modifying Files in Old Layers Costs You Twice

The Accidental Discovery

The Hazard "Optimization" Trap

Deep Dive: Why Modifications Pay a 100% Tax

The Clean Solution: Inline Interception

A Fuller Before-and-After

The Production Payoff

The Golden Rule of Layers

My Docker Build Was Slow Before It Even Started, Here's Why

The Setup

Attempt 1: Repo Root as Context

Attempt 2: Shrink the Context

Attempt 3: The Temporary Directory Hack

Attempt 4: Named Build Contexts

.dockerignore: Also About Context, Not Just Image Size

The Insight That Actually Mattered

What I Got Wrong Initially

The Mental Model I Use Now

Final Picture

Key Takeaways

The Recursive Mindset: Unlocking the Code You Already Know

The Philosophy: Why This Article Exists

The Setup

The Wrap-Up

3. What `can(x)` Actually Needs

10. The `Window` Class