Forem: Avinash Tyagi

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

Avinash Tyagi — Mon, 27 Apr 2026 12:57:54 +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

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.

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 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.