DEV Community: Avinash Tyagi

I Couldn't Optimize Max Sum Min-Product Until I Flipped the Question

Avinash Tyagi — Mon, 11 May 2026 03:01:14 +0000

This is part of a series where I break down coding concepts I understand when reading about them but struggle to reuse when I actually need them. Not tutorials. Personal learning journeys that break down the "why does this actually work" part.

The problem that tripped me up

LeetCode 1856: Maximum Subarray Min-Product. The formula is straightforward. For any subarray, multiply the minimum element by the sum of the subarray. Find the maximum across all possible subarrays.

I could see the O(n^2) solution clearly. Try every subarray, track the running min and running sum, update the max. But dropping to O(n)? That's where I got stuck.

Where my intuition went wrong

My first instinct was a sliding window approach. Add an element to the range, check if it improves the answer, otherwise store the max and reset. It felt right because you're building ranges and checking them.

But here's why it fails: the decision to "keep going or reset" depends on both the sum AND the minimum changing at the same time. Adding a large number helps the sum but might not help if the min stays low. Adding a small number hurts the min but you don't know yet whether the sum makes up for it. There's no clean greedy condition to check.

I was stuck because I was asking the wrong question.

The reframe that made it click

Instead of asking "what's the best range?", flip it:

For each element, what's the widest subarray where THAT element is the minimum?

Why does this cover every possible answer? Because whatever the optimal subarray is, it has some minimum element. That minimum is one of the values in the array. So if you check every element as a potential minimum and find its best subarray, you're guaranteed to find the answer.

This changes the problem from "search all subarrays" to "for each element, find its boundaries." And finding boundaries is exactly what a monotonic stack does.

How the monotonic stack finds boundaries

You maintain a stack of indices where the values are strictly increasing from bottom to top. As you iterate through the array, when you encounter a value smaller than or equal to the stack top, you pop.

The magic: when an element gets popped, it has found both its boundaries in that single moment.

Right boundary: the current element (the one causing the pop). It's smaller, so the popped element can't be the minimum past this point.
Left boundary: whatever is now on top of the stack after popping. It's the nearest smaller element to the left.

The subarray where the popped element is the minimum goes from left_boundary + 1 to right_boundary - 1.

Let me trace through [3, 1, 6, 4, 5, 2]:

i=0, val=3: push 0          stack: [0]
i=1, val=1: pop 0, push 1   stack: [1]
  → popped 3: right=1, left=-1 (empty stack), subarray=[0..0]
i=2, val=6: push 2          stack: [1, 2]
i=3, val=4: pop 2, push 3   stack: [1, 3]
  → popped 6: right=3, left=1, subarray=[2..2]
i=4, val=5: push 4          stack: [1, 3, 4]
i=5, val=2: pop 4           stack: [1, 3]
  → popped 5: right=5, left=3, subarray=[4..4]
         pop 3              stack: [1]
  → popped 4: right=5, left=1, subarray=[2..4]

When the stack is empty after popping, the left boundary is -1 (meaning "nothing smaller exists to the left, extend all the way to index 0"). After processing all elements, anything still in the stack has no right boundary, so it extends all the way to the end of the array (right boundary = n).

Prefix sums for O(1) range sums

Once you have boundaries for each element, you need the sum of that subarray. Building a prefix sum array with a leading zero handles this cleanly:

prefix = [0]
for num in nums:
    prefix.append(prefix[-1] + num)

# sum of nums[a..b] = prefix[b+1] - prefix[a]

The leading zero is important. Without it, getting the sum starting from index 0 requires special-case handling that leads to off-by-one bugs (I know because I made this exact mistake).

The full solution

def maxSumMinProduct(self, nums):
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)

    result = 0
    stack = []

    for i in range(len(nums)):
        while stack and nums[stack[-1]] >= nums[i]:
            popped = stack.pop()
            left = stack[-1] if stack else -1
            right = i
            total = prefix[right] - prefix[left + 1]
            result = max(result, nums[popped] * total)
        stack.append(i)

    # drain remaining elements
    while stack:
        popped = stack.pop()
        left = stack[-1] if stack else -1
        right = len(nums)
        total = prefix[right] - prefix[left + 1]
        result = max(result, nums[popped] * total)

    return result % (10**9 + 7)

Mistakes I actually made

Using > instead of >= in the while condition. With just >, equal elements don't get popped. This means when duplicates exist, a later equal element might compute an incorrect left boundary because its twin is still sitting in the stack.

Using the index as the value. I wrote result = max(result, popped * total) where popped is the index I popped from the stack. Should have been nums[popped]. The index is just a position. The value at that position is what you multiply by.

Prefix sum without the leading zero. My first attempt used pref_arr[0] = nums[0], which made the formula for getting sums starting from index 0 a special case. Adding the leading zero makes every range use the same formula: prefix[right] - prefix[left + 1].

What to practice next

These all use the same "for each element, find its boundaries" pattern with a monotonic stack:

Largest Rectangle in Histogram (LeetCode 84). The classic. For each bar, find the widest rectangle where it's the shortest bar. Almost identical logic.
Sum of Subarray Minimums (LeetCode 907). Instead of max(min * sum), you're summing all the min-products. Same boundary finding, different aggregation.
Sum of Subarray Ranges (LeetCode 2104). Find both the min-contribution and max-contribution of each element using two monotonic stacks (one increasing, one decreasing).
Trapping Rain Water (LeetCode 42). Uses a monotonic decreasing stack. When you pop, the boundaries tell you the width and height of water you can trap.
Next Greater Element II (LeetCode 503). Simpler. Good warm-up for understanding the pop mechanics without the prefix sum layer.

I'd recommend doing them in order: 84 first (it's the closest to what we just solved), then 907, then the rest.

I'm building Levelop to help people get better at problems like these. If you want more breakdowns like this, check it out.

Remove Duplicate Letters: I Knew Monotonic Stacks, But This Problem Still Got Me

Avinash Tyagi — Sat, 09 May 2026 03:26:08 +0000

I've been working through coding problems that I can understand when reading solutions but struggle to solve on my own. This series is about breaking down the "why does this actually work" part. Not tutorials. Just honest breakdowns of where my thinking got stuck and what finally unstuck it.

The problem that looked familiar

LeetCode 316: Remove Duplicate Letters. Given a string like "cbacdcbc", remove duplicate characters so every letter appears exactly once, and the result is the smallest possible in lexicographical order. The answer here is "acdb".

I'd just finished learning monotonic stacks for Sum of Subarray Minimums. Greedy popping, maintaining order, comparing against the stack top. I recognized the pattern immediately: scan the string, and if the current character is smaller than what's on the stack and the stack-top character appears later in the string, pop it. Classic monotonic stack.

So I coded it up, and it was wrong.

Where I got stuck

My first solution treated uniqueness as a cleanup step. I let duplicates pile up in the stack, then deduplicated at the end by reading from the bottom and skipping repeats. The stack logic would handle ordering, and the dedup pass would handle uniqueness. Two separate concerns, handled separately.

That's the thinking that broke it. In this problem, ordering and uniqueness aren't separate. They're coupled. The greedy decisions the stack makes (should I pop this character or keep it?) depend on knowing exactly which characters are already committed to the result. A duplicate sitting in the stack corrupts those decisions.

Duplicates poison the greedy logic

Here's the specific failure. Take "abacb".

With post-hoc deduplication, my stack processed it like this:

Step	Char	Stack action	Stack
1	a	push	[a]
2	b	a < b, push	[a, b]
3	a	b > a, pop b. a = a, push	[a, a]
4	c	a < c, push	[a, a, c]
5	b	c > b but c has freq 1, push	[a, a, c, b]

Dedup from the left: "acb".

The correct answer is "abc" (a at index 0, b at index 1, c at index 3).

What went wrong? Step 3 pushed a second a into the stack. That second a caused b to get popped unnecessarily. With b gone, it could only re-enter at the end, after c. The duplicate a sitting in the stack made the greedy logic produce a worse ordering.

If I'd skipped the second a entirely (it's already in the result, no need to process it), b would have stayed in the stack, and the final answer would have been "abc".

The seen-set: a co-pilot for the stack

The fix is a set that tracks what's currently in the stack. Before doing any work for a character, check the set. If the character is already there, skip it. Decrement its frequency (you've consumed this occurrence) and move on.

in_stack = set()

for char in s:
    freq[char] -= 1        # this occurrence is consumed
    if char in in_stack:    # already in the result
        continue
    # ... stack logic ...
    stack.append(char)
    in_stack.add(char)

This isn't just a performance optimization. It fundamentally changes what the stack sees. Without it, the stack is making ordering decisions with ghost characters that shouldn't be there.

Popping means evicting, and the set needs to know

Here's the second thing that got me. I added the set, but when I popped a character from the stack, I forgot to remove it from the set.

Think about what popping means in this problem. You're looking at the stack-top character and saying: "You're bigger than what I've got now, and you appear again later in the string. I'll use a later copy of you instead." That character is leaving your result. It's no longer committed. So when you encounter it again later, it needs to be allowed back in.

If the set still thinks it's in the stack, the later occurrence gets skipped. The character ends up nowhere.

Trace "cbacdcbc" with a stale set:

Step	Char	Action	Stack	Set
1	c	push	[c]	{c}
2	b	pop c (freq 3>1), push b	[b]	{c, b}
3	a	pop b (freq 2>1), push a	[a]	{c, b, a}
4	c	skipped (set says c is here)	[a]	{c, b, a}
5	d	push	[a, d]	{c, b, a, d}
6-8	c,b,c	all skipped	[a, d]	{c, b, a, d}

Result: "ad". The actual answer is "acdb".

Characters c and b were popped from the stack but never removed from the set. Every future occurrence got skipped. They vanished from the result entirely.

The fix: when popping, remove from the set before (or during) the pop.

while stack and stack[-1] > char and freq[stack[-1]] > 0:
    in_stack.remove(stack[-1])
    stack.pop()

The complete solution

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        freq = {}
        for c in s:
            freq[c] = freq.get(c, 0) + 1

        stack = []
        in_stack = set()

        for c in s:
            freq[c] -= 1
            if c in in_stack:
                continue
            while stack and stack[-1] > c and freq[stack[-1]] > 0:
                in_stack.remove(stack[-1])
                stack.pop()
            stack.append(c)
            in_stack.add(c)

        return ''.join(stack)

Three things work together: the stack maintains lexicographic order, the frequency map answers "is it safe to evict this character?", and the set tracks what's currently committed. Remove any one piece and the solution breaks.

The pattern underneath

Standard monotonic stack problems (next greater element, daily temperatures, histogram) only care about ordering. Every element eventually enters the stack exactly once. The stack just controls when elements leave and what order they end up in.

Remove Duplicate Letters adds a constraint: each character can appear in the result at most once. That single constraint means the stack can't operate alone anymore. It needs a partner that tracks membership, and that partner has to stay perfectly in sync. Every push updates the set. Every pop updates the set. If they drift, the greedy logic makes decisions based on a state that doesn't match reality.

This "stack + membership set" pattern shows up in a few other places. Anytime a monotonic stack problem adds a uniqueness or "already used" constraint, look for it.

What to practice next

These are ordered roughly by how they connect to the ideas above.

LC 1081, Smallest Subsequence of Distinct Characters (medium). Literally the same problem with a different name. Good for confirming you actually get it and didn't just memorize the solution for 316.
LC 402, Remove K Digits (medium). Monotonic stack with a removal budget instead of a uniqueness constraint. Tests whether you understand the greedy popping logic on its own.
LC 321, Create Maximum Number (hard). Combines monotonic stack selection from two arrays. The merging step is tricky.
LC 907, Sum of Subarray Minimums (medium). Classic monotonic stack without the uniqueness layer. If you haven't done this one, it's the best way to solidify the base pattern.
LC 84, Largest Rectangle in Histogram (hard). Another pure monotonic stack problem. Boundary finding in both directions.

I'm building Levelop to help people get better at problems like these. If you want more breakdowns like this, check it out.

I Understood Monotonic Stacks When I Stopped Thinking About Stacks

Avinash Tyagi — Thu, 30 Apr 2026 20:43:41 +0000

The problem

LeetCode 907: Sum of Subarray Minimums. Given an array, find the minimum of every contiguous subarray, and return the sum of all those minimums.

I could solve this in O(n²) almost immediately. Two nested loops, track the running minimum as you extend each subarray, add it to the total. Simple. But the optimal O(n) solution uses a monotonic stack, and I could not figure out why a stack had anything to do with finding minimums across subarrays.

Flipping the question

The brute force iterates over every subarray and asks "what's the minimum here?" The O(n) approach asks a completely different question: "for each element, how many subarrays is it the minimum of?"

These two questions give the same answer. If element 3 is the minimum of 5 subarrays, it contributes 3 × 5 = 15 to the total sum. Add up every element's contribution and you get the same result as checking every subarray individually.

This reframing is the entire foundation. Everything else builds on it.

Counting subarrays with the multiplication principle

Once you're asking "how many subarrays is arr[i] the minimum of?", it becomes a counting problem. For arr[i] to be the minimum of a subarray, that subarray can't contain anything smaller than arr[i]. So you look left and right from index i and find the boundaries: the nearest smaller element on each side.

Take [3, 1, 2, 4] and look at the element 2 at index 2.

To the left: index 1 has value 1, which is smaller. Can't extend past it.
To the right: index 3 has value 4, which is fine. Then we hit the end.

So 2 is the minimum of subarrays [2] and [2, 4]. Two subarrays.

But you don't need to list them out. You just need two numbers:

L = how many positions you can include to the left (including the element itself). Here, L = 1.
R = how many positions you can include to the right (including the element itself). Here, R = 2.

Total subarrays = L × R = 1 × 2 = 2.

This is the multiplication principle. You're picking a left endpoint (L choices) and a right endpoint (R choices) independently. Every combination gives a valid subarray where arr[i] is the minimum. Same math as "3 shirts and 4 pants = 12 outfits."

The bargain hunter in the mall

So the whole problem reduces to: for each element, find L and R. Which means finding the nearest smaller element to the left and right. The brute force way to do this is to scan in both directions from every index. That's O(n²), which defeats the purpose.

This is where the monotonic stack comes in. And the analogy that made it click for me was a bargain hunter walking through a mall.

Picture a long corridor of shops, all selling the same item at different prices. You're walking left to right. At each shop, you want to know: what's the nearest shop behind me that's cheaper?

You could turn around and check every shop you've passed. Or you could be smart about what you remember.

As you walk, you keep a mental list of shops worth remembering. The rule: when you see a new price, forget every remembered shop that's more expensive than it. Why? If shop A sells for $5 and shop B (closer to you, further down the corridor) sells for $3, shop A is dead forever. For any shop you visit in the future, you'd hit shop B first, and it's cheaper. Shop A can never be anyone's answer again.

What survives in your memory is always a list of prices in increasing order. The most recent one is the nearest cheaper option for wherever you're standing.

That mental list is the monotonic stack. You walk through the array once, and for each element, the stack tells you the nearest smaller element to the left. One pass, O(n).

For [3, 1, 2, 4]:

At index 0 (val 3): List empty. Nothing cheaper. L = 1. Remember $3.
At index 1 (val 1): $3 is more expensive than $1. Forget $3. List empty. Nothing cheaper. L = 2. Remember $1.
At index 2 (val 2): $1 is cheaper than $2. Keep it. Nearest cheaper = index 1. L = 2 - 1 = 1. Remember $2.
At index 3 (val 4): $2 is cheaper than $4. Keep it. Nearest cheaper = index 2. L = 3 - 2 = 1. Remember $4.

One left-to-right pass gives all L values. A right-to-left pass with the same logic gives all R values. Two passes, O(n) total.

The duplicate problem and the asymmetric fix

There's one tricky edge case. What happens when two elements have the same value?

Take [3, 1, 2, 1]. Both 1s could claim to be the minimum of the subarray [1, 2, 1]. If both claim it, you double-count.

The fix feels weird at first: make one side strict and the other inclusive. On the left pass, pop elements that are greater than or equal to the current value (so equal values don't block you). On the right pass, only pop elements that are strictly greater (so equal values do block you).

This means the left 1 can't extend past the right 1 on its right side, because equal counts as a boundary there. The right 1 can extend past the left 1 on its left side, because equal doesn't count as a boundary there. They split the territory cleanly.

I initially thought this was a hack. Two identical elements should split ownership evenly, right? But think of it like HR assigning projects to identical twins at a company. It doesn't matter who gets each project, as long as every project goes to exactly one person. No double billing, no gaps. The asymmetric rule is just a consistent tiebreaker.

This pattern shows up everywhere in competitive programming. The i < j constraint when counting pairs (the handshake problem), skipping duplicates in two-pointer solutions for 3Sum, lower_bound vs upper_bound in binary search. They're all the same idea: when multiple candidates could claim the same thing, pick a consistent tiebreaker so exactly one wins.

Knowing when (and when not) to reach for a monotonic stack

The core signal: "for each element, find the nearest element that beats it in some direction." If you can rephrase a problem as "nearest greater" or "nearest smaller" to the left or right, it's monotonic stack territory.

It shows up in several disguises. Stock span problems ("how many consecutive days had a lower price?"), temperature problems ("how many days until a warmer day?"), histogram problems ("how wide can this bar extend?"). They all reduce to finding boundaries.

Where it doesn't apply, even when it looks like it might:

Sliding window maximum uses a monotonic deque, not a stack. You need to remove from both ends. The "from both ends" requirement is the giveaway.

Min Stack has "min" and "stack" in the name, but it's a data structure design problem. You're not popping based on value comparisons.

Longest Valid Parentheses uses a stack, but not a monotonic one. Elements are pushed and popped based on matching rules, not because one element is "bigger" or "smaller" than another.

The quick filter: does the popping logic depend on comparing values for ordering? If yes, monotonic stack. If the popping is driven by something else (window boundaries, bracket matching, design constraints), it's a different tool.

What to practice next

These are ordered by difficulty, with notes on how each connects to what's covered above.

LC 496, Next Greater Element I (easy). Direct "next greater" application. Good warm-up.
LC 739, Daily Temperatures (medium). Next greater element with distance calculation.
LC 901, Stock Span Problem (medium). Previous greater element. Tests if you can flip the direction.
LC 84, Largest Rectangle in Histogram (hard). Same L/R boundary finding, applied to area. Very close to Sum of Subarray Minimums.
LC 2104, Sum of Subarray Ranges (medium). Four monotonic stack passes: L and R for minimums, L and R for maximums.
LC 503, Next Greater Element II (medium). Circular array twist. Handle it by looping through the array twice using i % n.
LC 42, Trapping Rain Water (hard). Try solving it with a monotonic stack after the others.

I've been working through these on Levelop and this one really forced me to understand the "why" behind the pattern, not just the template.

I Tried Two Pointers on a DP Problem and Learned What "Subset" Actually Means

Avinash Tyagi — Wed, 29 Apr 2026 12:46:13 +0000

The problem

LeetCode 416: Partition Equal Subset Sum. Given an array of positive integers, determine if you can split it into two subsets with equal sum.

My first instinct: use two pointers. One starting from the left, one from the right. Grow each window. Whichever side has the smaller sum, expand that pointer. When they meet, check if the sums are equal.

I even thought about sorting first to make the approach work better. It felt clean. It felt efficient. It was completely wrong.

Why two pointers don't work here

Take [2, 3, 5, 7, 1, 6]. Total is 24, so each subset needs to sum to 12. The answer is true: {5, 7} and {2, 3, 1, 6}.

Sorted: [1, 2, 3, 5, 6, 7]. Running two pointers from both ends, the sums land at 11 and 13. They never balance. But the valid partition exists. It just requires picking the 5 and 7 from the middle while leaving everything else.

Two pointers assume you're splitting at some dividing line. Everything left goes in one group, everything right goes in the other. But "subset" means you can cherry-pick from anywhere. The 5 and the 7 aren't adjacent in the sorted array, and they definitely aren't on the same side of any split point.

That distinction between "split at a point" and "pick from anywhere" is what I missed entirely.

The real question hiding inside this problem

Once the subset framing clicked, the problem simplified. If the total sum is S, each subset needs to be S/2. And if S is odd, you can stop immediately. You can't split an odd number into two equal integers.

So the problem reduces to: can I find any subset of nums that adds up to exactly S/2?

That's subset sum. And subset sum is a DP problem.

Starting with plain recursion

Before any DP, I wrote the simplest version. For each element, you have two choices: include it in the subset or skip it. Include means the remaining target shrinks by that element's value. Skip means the target stays the same.

def canReach(index, target):
    if target == 0:
        return True
    if index >= len(nums) or target < 0:
        return False

    include = canReach(index + 1, target - nums[index])
    skip = canReach(index + 1, target)
    return include or skip

The or is because we only need one path to work. If including element 3 eventually leads to a valid subset, we don't care what skipping it would have done.

This works. It's also slow. For [1, 5, 5, 11] with target 11, the recursion tree branches twice at every element. That's 2^n paths. But more importantly, some of those paths ask the same question. "Can I reach target 5 starting from index 3?" shows up from multiple branches. Pure recursion answers it every time from scratch.

Adding memoization

The fix is three lines. Before computing, check if you've seen this (index, target) pair before. After computing, store the result.

def canReach(index, target):
    if target == 0:
        return True
    if index >= len(nums) or target < 0:
        return False
    if (index, target) in memo:
        return memo[(index, target)]

    result = canReach(index + 1, target - nums[index]) or canReach(index + 1, target)
    memo[(index, target)] = result
    return result

Same recursion. Same logic. Just remembering answers. This is the top-down DP approach.

The bottom-up version (and where I got confused)

The array-based DP flips the approach. Instead of recursing and caching, you build a boolean array where dp[s] answers: "can I reach sum s with the elements I've processed so far?"

dp = [False] * (target + 1)
dp[0] = True

for num in nums:
    for s in range(target, num - 1, -1):
        if dp[s - num]:
            dp[s] = True

return dp[target]

I understood what the code does. I could trace through it. But the line dp[s - num] felt disconnected from anything I could reason about. In my previous DP problem (decode ways), dp[i] meant "position i in the string." The index was a location. Here, the index IS the sum. That shift messed with my mental model.

The cashier analogy

What made it click was thinking about making exact change.

You're a cashier. A customer owes you $11. You have coins worth $1, $5, $5, and $11. You can only use each coin once. Can you make exactly $11?

You start knowing you can make $0 (by using nothing). Then you pick up each coin one at a time and ask: "what new amounts can I make now?"

Before any coins: {0}
Pick up the $1 coin: everything I could make before, plus everything-plus-1. So {0, 1}.
Pick up the first $5 coin: {0, 1, 5, 6}.
Pick up the second $5 coin: {0, 1, 5, 6, 10, 11}.

11 is in the set. Done.

Each time you pick up a coin, the old amounts stay (that's skipping the coin) and new amounts appear (that's including it). The same two choices as the recursion, just expressed as a growing set of reachable values.

Now dp[s - num] has a natural reading: "I want to make $s. I'm holding a $num coin. Can I cover the rest?" If dp[s - num] is true, then yes, adding this coin gets me to $s.

The backwards loop

This was the other thing that felt arbitrary until I traced through what goes wrong without it.

Say dp = [True, False, False, ...] and you process the $1 coin. If you loop forwards (small to large):

s=1: dp[0] is True, so dp[1] = True. Fine.
s=2: dp[1] is True (you just set it), so dp[2] = True. Wait.
s=3: dp[2] is True (just set again), so dp[3] = True.

You used the $1 coin three times. You only have one.

The problem is you're reading values you wrote during the same round. Each "yes" you write feeds the next check, and the coin keeps getting reused.

Going backwards (large to small): when you set dp[s] = True, the values you read from (dp[s - num]) are at smaller indices. You already passed those indices. You haven't touched them this round. So you're always reading "yesterday's answers," not the ones you just wrote.

The mental image that stuck: backwards means each coin goes back in the drawer after you check it. You can't accidentally grab it again. Forwards means the coin stays on the counter, and you keep picking it up.

The cheatsheet

This generalizes to a simple rule:

Can each item be used only once? Loop backwards. This is 0/1 knapsack, partition subset sum, target sum.

Can items be reused? Loop forwards. This is coin change, unbounded knapsack, combination sum.

One question. One answer. That's the entire decision.

The complete solution

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 == 1:
            return False

        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True

        for num in nums:
            for s in range(target, num - 1, -1):
                if dp[s - num]:
                    dp[s] = True

        return dp[target]

What I got wrong along the way

My first attempt at the DP had dp[target - i] instead of dp[i - num]. The difference matters. dp[i - num] asks "was the sum that's num less than i reachable?" That's the include question: if I can reach 1, and I have a 5-coin, I can reach 6. My wrong version was asking a completely unrelated question about a completely unrelated index.

The fix came from going back to the cashier framing. "I want $6. I have $5. Can I cover the remaining $1?" That's dp[6 - 5]. Not dp[11 - 6].

What to practice next

These all use the same "items toward a target" DP pattern, ordered by difficulty:

LeetCode 494 (Target Sum): Same include/skip structure. Each element is either added or subtracted. The target just shifts.
LeetCode 322 (Coin Change): Unlimited reuse, so the loop goes forwards. Good for locking in the direction rule.
LeetCode 474 (Ones and Zeroes): 0/1 knapsack but with two dimensions (count of 0s and 1s). Same backwards loop, just a 2D array.
LeetCode 518 (Coin Change II): Counting combinations instead of just true/false. Forwards loop, addition instead of boolean OR.

I'm building Levelop to help people get better at problems like these. If you want more breakdowns like this, check it out.

I Couldn't See Why dp[i] = dp[i+1] + dp[i+2] Actually Counts Anything

Avinash Tyagi — Tue, 28 Apr 2026 20:03:27 +0000

The problem

LeetCode 91: Decode Ways. You get a string of digits. Each digit or pair of digits maps to a letter (1 = A, 2 = B, ... 26 = Z). Count how many ways you can decode the entire string.

When I first read this, I thought: find all the different permutations and combinations of the input string, filter out the ones that are one or two digits, count them. If it starts with 0, return 0.

That's wrong in a very specific way. The string order is fixed. You never rearrange anything. You're deciding where to place the splits.

Partitioning, not permutations

Take "226". You're not shuffling characters around. You're choosing how to chop the string into consecutive pieces, left to right, where each piece is one or two digits between 1 and 26.

2 | 2 | 6 → B, B, F
22 | 6 → V, F
2 | 26 → B, Z

Three ways. Every digit is used exactly once. Every piece is consumed in order.

This seems obvious once you see it, but my first instinct was to think about substrings and combinations. The shift to "I'm just deciding where to put dividers in a fixed sequence" changed how I thought about the whole problem.

The binary choice at each position

Once partitioning clicks, the structure gets simple. At every position in the string, you have exactly two options: take one digit or take two digits. That's it. Then you repeat from wherever you land.

At position 0 of "226":

Take "2" (one digit) → now you're at position 1 with "26" remaining
Take "22" (two digits) → now you're at position 2 with "6" remaining

Each of those remaining strings has its own set of choices. If you draw this out, it forms a binary tree. Every path from the root to a leaf where you've consumed the entire string is one valid partition.

I could see this. I could draw the tree. I could count partitions by hand. What I could not figure out was why the DP formula dp[i] = dp[i+1] + dp[i+2] actually produces the right count. It looked like it should work. I could verify it on examples. But I couldn't explain why.

The part where I got stuck

The DP says: dp[i] is the number of ways to decode the string starting from position i. Fill right to left. Base case: dp[n] = 1 (you've consumed everything, that counts as one completed partition).

The recurrence:

dp[i] = 0
if s[i] != '0':           dp[i] += dp[i+1]   # take 1 digit
if s[i:i+2] is 10–26:     dp[i] += dp[i+2]   # take 2 digits

I could fill in the array mechanically. For "1226":

dp[4] = 1
dp[3] = 1
dp[2] = 2
dp[1] = 3
dp[0] = 5

Correct answer: 5. But why does adding two values from the right give you the count of all partitions? I stared at visual walkthroughs and formula breakdowns and nothing was landing.

What actually made it click: the addition principle

The breakthrough had nothing to do with DP specifically. It came from a much more basic idea.

You have 3 red shirts and 2 blue shirts. How many shirts can you pick? You say 3 + 2 = 5. This works because no shirt is both red and blue. The groups don't overlap.

That's the addition principle. If you can split a counting problem into non-overlapping groups, the total count is the sum of the group counts.

Now, at position i in the string, every partition that passes through this position does exactly one of two things: it takes one digit or it takes two digits. Not both. These are two non-overlapping groups.

Group A (took one digit): all partitions where the first chunk starting at i is a single digit. How many partitions are in this group? However many ways you can finish the rest of the string from position i+1. That's dp[i+1].
Group B (took two digits): all partitions where the first chunk starting at i is a two-digit number. How many? However many ways to finish from position i+2. That's dp[i+2].

Every partition is in exactly one group. No overlap, no gaps. So the total is the sum: dp[i] = dp[i+1] + dp[i+2].

That's it. The addition isn't some DP trick. It's the same logic as counting shirts. You're splitting the partitions into two non-overlapping groups based on the choice made at this position.

Addition vs. multiplication (and why this matters for other DP problems)

While working through this, I realized the addition principle has a sibling that shows up in different DP problems: the multiplication principle.

Addition: you're choosing between alternatives. Red shirt OR blue shirt. Take 1 digit OR take 2 digits. The groups compete for one slot. You add.

Multiplication: you're combining independent sequential choices. Pick a shirt AND pick pants. 3 shirts × 4 pants = 12 outfits. The choices don't compete. They stack.

The question to ask yourself at each step of a DP recurrence: "Am I looking at alternatives (OR) or combinations (AND)?"

Decode ways is pure OR. At each position, you do one thing or the other. So the formula is a sum.

Something like "how many n-character PINs can you make with 5 vowels for position 1 and 10 digits for position 2?" is pure AND. You need both positions filled, every vowel pairs with every digit. So it's a product: dp[i] = dp[i-1] × choices[i].

The paint fence problem (no three consecutive posts the same color) uses both. At each post, the total splits into two groups (same as previous OR different from previous, that's addition). Within the "different" group, each valid history combines with each color choice (that's multiplication). So the recurrence has both: diff[i] = (same[i-1] + diff[i-1]) × (k-1).

Recognizing which principle applies at each piece of a recurrence is what turns "I can verify it works" into "I understand why it works."

The base case makes sense now too

dp[n] = 1 confused me initially. You're past the end of the string. There's nothing left. Why is that 1 and not 0?

Because it's the "I made it" signal. If a path of choices led you all the way past the last digit, that path consumed everything and represents one complete partition. If dp[n] were 0, every path would add up to 0 and nothing would ever get counted.

Think of it like the road fork analogy. If you take a path and it leads to an exit, that exit counts as 1. The exit existing is what makes the path worth counting.

The direction question

One more thing that wasn't obvious: why fill right to left?

It depends on how you define dp[i]. I defined it as "ways to decode from position i to the end." That means dp[i] depends on dp[i+1] and dp[i+2], both of which are to the right. So those need to exist before you compute dp[i]. Right to left.

But you could define it the other way: dp[i] = ways to decode from the start up to position i. Now your answer at i depends on dp[i-1] and dp[i-2], both to the left. Fill left to right. Same final answer, different direction.

The direction isn't a property of the problem. It's a property of how you phrase the question dp[i] is answering. "How many ways to get here?" looks backward. "How many ways from here to the end?" looks forward.

The code

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[n] = 1

        if s[n - 1] != '0':
            dp[n - 1] = 1

        for i in range(n - 2, -1, -1):
            if s[i] != '0':
                dp[i] += dp[i + 1]
            two_digit = int(s[i:i + 2])
            if 10 <= two_digit <= 26:
                dp[i] += dp[i + 2]

        return dp[0]

Practice problems

In order of difficulty, all using similar DP thinking:

LeetCode 70 (Climbing Stairs): Same recurrence structure as decode ways but without validity checks. Pure dp[i] = dp[i-1] + dp[i-2]. Good for building muscle memory on the pattern.
LeetCode 198 (House Robber): 1D DP with "take or skip" choices at each position. The OR/addition principle applies the same way.
LeetCode 256 (Paint House): Tracking states (which color was last used) similar to the paint fence same/diff tracking. Uses both addition and multiplication thinking.
LeetCode 639 (Decode Ways II): Decode ways but with wildcard characters. Same core logic, more validity branches to handle.

I'm building Levelop to help people get better at problems like these. If you want more breakdowns like this, check it out.

I Knew BFS Existed but Couldn't Wire It Into a Grid Problem

Avinash Tyagi — Mon, 27 Apr 2026 12:57:54 +0000

The problem

LeetCode 1091: Shortest Path in Binary Matrix. You get an n×n grid of 0s and 1s. Find the shortest path from the top-left corner to the bottom-right corner, moving through cells with value 0. You can move in all 8 directions (up, down, left, right, and all four diagonals). Return the number of cells in the path, or -1 if no path exists.

I looked at this and thought: okay, at every cell that's a 0, I check the connected neighbors. Skip anything out of bounds or already visited. Straightforward enough.

But when I actually sat down to write it, two things tripped me up. I didn't know how to pick BFS over DFS for this. And even after choosing BFS, I had no idea how to track the path length.

"Shortest" is doing the work

My first instinct was just "explore the neighbors." I hadn't committed to BFS or DFS. Both would find a path. But the problem says shortest, and that word changes everything.

DFS goes deep. It picks one direction and follows it as far as possible before backtracking. It'll find a path, but it might be a terrible one. To guarantee the shortest, you'd have to explore every possible path and compare. That's expensive.

BFS explores in waves. Wave 1 is everything 1 step from the start. Wave 2 is everything 2 steps away. Wave 3, everything 3 steps. The first time you reach the destination, you got there in the fewest steps possible. You never need to compare alternatives because you tried all shorter routes first.

That's the core insight: BFS gives you shortest path for free. You don't need extra logic to compare paths or track the minimum. The structure of the algorithm handles it.

"How do I track the distance though?"

This was my actual sticking point. I had a queue. I was popping cells and pushing neighbors. The BFS loop worked. But I couldn't figure out where the path length came from.

My queue held coordinates like [i, j]. When I reached the bottom-right corner, I had no way to know how many steps it took to get there.

The fix is simple once you see it: store the distance with each item in the queue. Instead of [i, j], push [i, j, distance]. The start cell goes in as [0, 0, 1] (distance 1 because the problem counts the start cell). When you process a cell at distance d and add its neighbors, each neighbor gets d + 1. When you pop the destination cell, its distance is your answer.

queue.append([0, 0, 1])  # row, col, distance

# later, when adding neighbors:
queue.append([ni, nj, curr_distance + 1])

That's it. The distance piggybacks on the BFS traversal. No separate tracking needed.

The full solution

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] != 0:
            return -1

        n = len(grid)
        queue = deque()
        queue.append([0, 0, 1])
        grid[0][0] = -1  # mark visited

        while len(queue) > 0:
            curr = queue.popleft()
            i, j, dist = curr[0], curr[1], curr[2]

            if i == n - 1 and j == n - 1:
                return dist

            for di in [-1, 0, 1]:
                for dj in [-1, 0, 1]:
                    if di == 0 and dj == 0:
                        continue
                    ni, nj = i + di, j + dj
                    if ni >= 0 and ni < n and nj >= 0 and nj < n:
                        if grid[ni][nj] == 0:
                            queue.append([ni, nj, dist + 1])
                            grid[ni][nj] = -1

        return -1

Walk through a small grid to see the waves:

[0, 0, 1]
[0, 1, 0]
[0, 0, 0]

Wave 1 (distance 1): (0,0).
Wave 2 (distance 2): (0,1), (1,0).
Wave 3 (distance 3): (2,0), (2,1).
Wave 4 (distance 4): (2,2), (1,2).

BFS reaches (2,2) at distance 4. That's the answer.

Mistakes I made that are probably common

Counting edges instead of cells. I initially set the starting distance to 0. For the grid above, that gives 3 instead of 4. The LeetCode problem counts cells visited (both endpoints), not hops between them. This is the kind of off-by-one that makes you fail test cases and stare at correct-looking code for ten minutes.

Marking cells as visited when popping, not when enqueueing. This is subtle. Say cell (1,1) is a neighbor of both (0,0) and (0,1). If you process (0,0) first and add (1,1) to the queue but don't mark it visited yet, then when you process (0,1), you add (1,1) again. Now it's in the queue twice, and all its neighbors get processed twice too. The fix: mark a cell visited the moment you add it to the queue, not when you pop it.

Off-by-one on the destination check. If the grid is 5×5, the bottom-right is (4,4), not (5,5). Checking i == len(grid) instead of i == len(grid) - 1 means you never find the destination. Obvious in hindsight. Not obvious at 11pm.

Using list.pop(0) instead of collections.deque. A regular Python list pops from the front in O(n) because it shifts every remaining element. On a big grid, this quietly turns your O(n) BFS into O(n²). deque.popleft() is O(1). Small change, big difference.

When BFS works (and when it doesn't)

BFS gives shortest path when all edges have the same weight. In a grid where every step costs 1, that holds. If some steps cost more than others (weighted graph), BFS won't work. You'd need Dijkstra's algorithm instead.

The BFS template itself stays remarkably stable across problems. Once you have the loop, the only things that change are:

Where you start. One cell? Multiple cells at once? Every cell of a certain type? (Multi-source BFS seeds the queue with all starting points at distance 0.)

Where you stop. Reached a specific cell? All targets converted? Queue is empty?

Which directions. 4-directional (up/down/left/right) or 8-directional (including diagonals)?

The loop, the queue, the visited tracking, the distance propagation: all identical every time.

Practice problems

In order of difficulty, all using BFS on grids:

LeetCode 994 (Rotting Oranges): Multi-source BFS. All rotten oranges start spreading simultaneously. Same wave-by-wave expansion, but you seed the queue with every rotten cell instead of one corner.
LeetCode 542 (01 Matrix): Find the shortest distance from every cell to the nearest 0. Multi-source BFS starting from all 0-cells.
LeetCode 1162 (As Far from Land as Possible): Multi-source BFS from all land cells. The answer is the last wave number. Same pattern, different framing.
LeetCode 752 (Open the Lock): BFS on a non-grid graph. Each "node" is a 4-digit lock combination. Neighbors are one-digit turns. Tests whether you see that BFS works on any graph, not just grids.
LeetCode 127 (Word Ladder): BFS on words where neighbors differ by one letter. Harder to see the graph structure, but the BFS mechanics are identical.

I'm building Levelop to help people get better at problems like these. If you want more breakdowns like this, check it out.

Why I Stopped Trying to Count "Exactly Right" and Started Subtracting

Avinash Tyagi — Sun, 26 Apr 2026 10:21:20 +0000

The problem that broke my brain

LeetCode 795: Number of Subarrays with Bounded Maximum. You get an array of integers and a range [left, right]. Count how many contiguous subarrays have their maximum element within that range.

I understood what the problem was asking. I could verify answers by hand. But when I sat down to code it, I kept getting tangled. My sliding window logic was a mess because every element fell into one of three buckets: too small (below left), just right (in the range), or too big (above right). Each bucket needed different handling, and my code reflected that confusion.

Three zones, two problems

Here's what made this problem feel harder than it should be. When an element is bigger than right, it's a hard wall. No valid subarray can include it. You reset everything.

But when an element is smaller than left? It's fine. It just can't be the maximum. A subarray like [2, 1, 1] with left=2, right=3 is perfectly valid because the max is 2. The small elements are just passengers.

So "not in range" actually means two completely different things depending on which side you fall on. Trying to handle both cases in one pass meant tracking which elements were carrying the subarray (in-range elements) separately from which elements were just tagging along (too-small elements). Every if/else branch got another condition. The logic kept growing.

That's when I realized: maybe counting "exactly in range" directly is the wrong approach.

What if you only had one boundary?

Consider a simpler question: how many subarrays have their maximum ≤ some value k?

This is dramatically easier. There's only one type of violation. If an element is ≤ k, it extends your current valid window. If it's > k, the window breaks. Two states, one condition.

And here's the counting trick that makes it fast. At each position i, the number of valid subarrays ending at that position equals the current window length. If you've had 4 consecutive elements all ≤ k, there are exactly 4 subarrays ending at position 3: the single element, the pair ending here, the triple, and all four together.

def count_at_most(nums, k):
    run = total = 0
    for x in nums:
        run = run + 1 if x <= k else 0
        total += run
    return total

That's the entire helper. Walk through nums = [2, 1, 1, 3] with k = 3:

Position	Element	≤ 3?	Run	Subarrays ending here
0	2	yes	1	`[2]`
1	1	yes	2	`[1], [2,1]`
2	1	yes	3	`[1], [1,1], [2,1,1]`
3	3	yes	4	`[3], [1,3], [1,1,3], [2,1,1,3]`

Total: 1 + 2 + 3 + 4 = 10. Every subarray in the entire array has max ≤ 3.

The subtraction

Now the key move. "Max is in [left, right]" means "max ≤ right" AND "max ≥ left." That second condition is the annoying one. But you can rewrite it:

subarrays where max is in [left, right] = subarrays where max ≤ right minus subarrays where max ≤ left - 1

The first count includes everything up to right. The second count captures the ones that are too small (max below left). Subtracting removes exactly those.

Same array, left = 2, right = 3:

atMost(3) = 10 (computed above)

atMost(1):

Position	Element	≤ 1?	Run	Count
0	2	no	0	0
1	1	yes	1	1
2	1	yes	2	2
3	3	no	0	0

Total: 3.

Answer: 10 - 3 = 7. The valid subarrays are [2], [2,1], [2,1,1], [2,1,1,3], [1,1,3], [1,3], [3].

The full solution is five lines:

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        def count_at_most(k):
            run = total = 0
            for x in nums:
                run = run + 1 if x <= k else 0
                total += run
            return total

        return count_at_most(right) - count_at_most(left - 1)

Where else this works (and where it doesn't)

This decomposition isn't specific to "bounded max." It works anywhere you need to count subarrays defined by a range, as long as the "at most" version behaves nicely with a sliding window.

LeetCode 992 (Subarrays with Exactly K Distinct Integers) is the same idea wearing different clothes. Counting "exactly K distinct" directly is painful because valid subarrays form a band in the middle of your window. Some shorter subarrays ending at the same position might have fewer than K distinct elements. Some longer ones might have more. You'd need two left pointers to track both edges of that band.

But "at most K distinct" is a clean sliding window. One left pointer, shrink when you exceed K. So: exactly(K) = atMost(K) - atMost(K - 1).

LeetCode 1248 (Count Number of Nice Subarrays) is the same pattern again, just counting odd numbers instead of distinct elements.

The pattern works because of a property called monotonicity: if a window satisfies "max ≤ k," every sub-window inside it also satisfies "max ≤ k." Same for "distinct count ≤ k." Shrinking the window from the left can never violate the property if it already holds.

This breaks for something like "median ≤ k." Removing an element from the left of a window can increase or decrease the median unpredictably. You can't maintain a valid window by just shrinking, so the sliding window approach falls apart, and the subtraction decomposition with it.

The general rule: if a range constraint is making your counting hard, check whether you can split it into two one-sided constraints. If each one-sided version has the monotonicity property (valid window implies all sub-windows are valid), the decomposition works.

Practice problems

In order of difficulty, all using this pattern:

LeetCode 713 (Subarray Product Less Than K): Single-sided, products instead of max. The "subarrays ending here = window size" insight is the same.
LeetCode 2110 (Number of Smooth Descent Periods): Run-length counting, almost identical to the count_at_most helper.
LeetCode 992 (Subarrays with Exactly K Distinct Integers): The classic atMost(K) - atMost(K-1). Needs a hashmap for frequencies.
LeetCode 1248 (Count Number of Nice Subarrays): Same decomposition, counting odd numbers.
LeetCode 2444 (Count Subarrays With Fixed Bounds): Harder. Two simultaneous constraints without the subtraction shortcut. Tests whether you can extend the thinking.

I'm building Levelop to help people get better at problems like these. If you want more breakdowns like this, check it out.

I Couldn't Count Subarrays Until I Thought About Handshakes

Avinash Tyagi — Sat, 25 Apr 2026 10:04:37 +0000

Hi everyone, I'm starting a series where I break down the core intuition behind coding patterns I've struggled to truly understand or reuse confidently. Not just the "how" but the "why does this actually work" part. Starting with one that tripped me up longer than I'd like to admit.

I Couldn't Count Subarrays Until I Thought About Handshakes

I understood the concept behind "Subarrays Divisible by K" for a while. Prefix sums, mod k, check for matching remainders. Cool. But every time I tried to write the actual counting logic, I'd freeze. Why does count += map[remainder] work? Why not count += 1? Where does the formula come from?

It finally clicked when I stopped thinking about arrays and started thinking about people in a room.

The gap in my understanding

Here's what I already knew: if two prefix sums have the same remainder when divided by k, the elements between them sum to a multiple of k. Standard prefix sum trick.

What I didn't get was the leap from "find matching remainders" to "count all valid subarrays." I could identify that a valid subarray existed, but not how to count all of them efficiently.

Turns out I was missing some pretty basic math.

Lesson 1: The Handshake Problem

5 people in a room. Everyone shakes hands with everyone else exactly once. How many handshakes?

The formula is n * (n-1) / 2. For 5 people, that's 10. But the formula alone wasn't what helped me. What helped was seeing it built incrementally:

Person A enters. Nobody there. 0 handshakes.
Person B enters. Shakes hands with A. +1.
Person C enters. Shakes hands with A and B. +2.
Person D enters. Shakes with A, B, C. +3.
Person E enters. Shakes with A, B, C, D. +4.

Total: 0 + 1 + 2 + 3 + 4 = 10.

That's the same as 5×4/2 = 10. The incremental version and the formula give the same answer, just computed differently.

This is exactly what the hashmap does. When you write count += map[remainder], you're saying: "this new prefix sum just walked into the room. How many prefix sums with the same remainder are already here? Shake hands with all of them."

You don't add 1. You add however many are already waiting.

Lesson 2: Modular Arithmetic (Remainder Buckets)

When you divide any integer by k, the remainder is always between 0 and k-1. So every number falls into one of k "buckets."

The rule that matters: if two numbers have the same remainder mod k, their difference is always divisible by k.

14 % 5 = 4
 9 % 5 = 4
14 - 9 = 5   → divisible by 5 ✓

This works every time, not just with convenient examples. If a % k == b % k, then (a - b) % k == 0. Always.

This is why we care about prefix sum remainders. The subarray sum between index i and j is prefix[j] - prefix[i]. If both prefix sums land in the same remainder bucket, their difference (the subarray sum) is divisible by k.

Putting It Together

So the algorithm becomes:

Compute prefix sums and their remainders (that's the mod arithmetic)
Group them into remainder buckets
Count pairs within each bucket (that's the handshake problem)

The hashmap approach does step 3 incrementally. Here's a concrete walkthrough with arr = [4, 5, 0, -2, -3, 1], k = 5:

Start: map = {0: 1}   (prefix[-1] = 0, remainder 0)

i=0: prefix=4,  rem=4, map[4]=0  → count += 0, map={0:1, 4:1}
i=1: prefix=9,  rem=4, map[4]=1  → count += 1, map={0:1, 4:2}
i=2: prefix=9,  rem=4, map[4]=2  → count += 2, map={0:1, 4:3}
i=3: prefix=7,  rem=2, map[2]=0  → count += 0, map={0:1, 4:3, 2:1}
i=4: prefix=4,  rem=4, map[4]=3  → count += 3, map={0:1, 4:4, 2:1}
i=5: prefix=5,  rem=0, map[0]=1  → count += 1, map={0:2, 4:4, 2:1}

Total: 0 + 1 + 2 + 0 + 3 + 1 = 7

Look at remainder 4. It appeared 4 times total (at prefix indices 0, 1, 2, 4). The incremental additions for that bucket alone were 0, 1, 2, 3 which sums to 6. And 4×3/2 = 6. Same answer. The handshake formula, built up one step at a time.

The {0: 1} Seed

One thing that confused me initially: why do we start the map with {0: 1}?

Because there's a "virtual" prefix sum before index 0, which equals 0. If any prefix sum itself is divisible by k (remainder 0), it needs something to pair with. That virtual prefix[-1] = 0 is the pairing partner. Without it, you'd miss all subarrays that start from index 0.

Extending to "Subarray Sum Equals K" (LeetCode 560)

Once you get the divisible-by-k version, this one is a small twist. Instead of "same remainder," you look for a specific difference:

Divisible by K: prefix[j] % k == prefix[i] % k  →  look up same remainder
Sum Equals K:   prefix[j] - prefix[i] == k      →  look up (prefix[j] - k)

The code:

def subarraySum(nums, k):
    freq = {0: 1}
    prefix = 0
    count = 0
    for num in nums:
        prefix += num
        count += freq.get(prefix - k, 0)
        freq[prefix] = freq.get(prefix, 0) + 1
    return count

Same three ingredients: prefix sums give you the "what to track," the lookup condition tells you "what to search for," and the frequency map handles "how to count" (handshakes, not just existence).

Important: use a frequency dict, not a set. I made this mistake. A set only tells you "yes, it exists." A dict tells you "it exists 3 times," which means 3 valid subarrays, not 1. That's the handshake lesson all over again.

The Math Foundation I Was Missing

If you're stuck on these problems like I was, here's the learning order that worked for me:

Pair counting (n choose 2): Get comfortable with why "n people, count handshakes" = n(n-1)/2, and why building it as 0+1+2+...+(n-1) gives the same answer.
Modular arithmetic: Drill the rule "same remainder means difference is divisible by k" until it's automatic.
Connecting the two: Subarray problems ask you to count pairs of prefix sums that satisfy some condition. Once you see that, the hashmap is just the efficient way to count those pairs on the fly.

Problems to Practice

These all use the same pattern, roughly in order of difficulty:

LeetCode 560 - Subarray Sum Equals K (the classic)
LeetCode 974 - Subarrays Sums Divisible by K
LeetCode 525 - Contiguous Array (convert 0s to -1s, then it's sum equals 0)
LeetCode 1248 - Count Number of Nice Subarrays
LeetCode 1010 - Pairs of Songs Divisible by 60 (pure remainder + pairs, no prefix)
LeetCode 437 - Path Sum III (same technique, but on a tree)

The underlying skill isn't memorizing the prefix sum trick. It's recognizing when a subarray condition can be rewritten as a pairwise condition on prefix values, and then counting those pairs with a hashmap.

That recognition is what these problems are really testing.

I'm building Levelop to help people get better at problems like these. If you want more breakdowns like this, check it out.