Grid BFS problems look different on the surface — count islands, measure areas, rot oranges, paint pixels. But they're all the same skeleton with small twists. I went through four of them back to back, and by the fourth one I was only tracking the diff from the previous problem. That's the way to learn this family.
Most grid BFS code follows this exact skeleton:
queue = collections.deque([start])
mark start as visited
while queue:
row, col = queue.popleft()
for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
newRow, newCol = row + dr, col + dc
if inside grid and meets condition and not visited:
mark as visited # ← at ENQUEUE time, always
queue.append((newRow, newCol))One rule before anything else: mark cells visited when you add them to the queue, not when you take them out. Mark on dequeue and the same cell can enter the queue several times before it's processed. The answer still comes out right — it just silently wastes time and memory, which makes it the worst kind of bug.
200. Number of Islands
The base problem. I wrote a full breakdown in a separate post, so just the essence here — the whole algorithm is three sentences: scan every cell; unvisited land means a new island, count it; BFS from there to consume the entire island so it never gets counted again.
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
visited = set()
result = 0
def bfs(r, c):
queue = collections.deque([(r, c)])
visited.add((r, c))
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
while queue:
row, col = queue.popleft()
for dr, dc in directions:
newRow, newCol = row + dr, col + dc
if (0 <= newRow < rows and
0 <= newCol < cols and
grid[newRow][newCol] == '1' and
(newRow, newCol) not in visited):
visited.add((newRow, newCol))
queue.append((newRow, newCol))
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1' and (r, c) not in visited:
bfs(r, c)
result += 1
return resultTime: O(m·n) / Space: O(m·n)
Number of BFS calls == number of islands. Everything else in this post is a variation on this code.
695. Max Area of Island
Same skeleton, but BFS now returns a value. Exactly four lines change:
area = 1before the loop — the starting cell is land tooarea += 1on every enqueuereturn areaat the end of bfs- main loop keeps
maxArea = max(maxArea, bfs(r, c))instead of counting
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
visited = set()
maxArea = 0
def bfs(r, c) -> int:
queue = collections.deque([(r, c)])
visited.add((r, c))
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
area = 1
while queue:
row, col = queue.popleft()
for dr, dc in directions:
newRow, newCol = row + dr, col + dc
if (0 <= newRow < rows and
0 <= newCol < cols and
grid[newRow][newCol] == 1 and
(newRow, newCol) not in visited):
visited.add((newRow, newCol))
queue.append((newRow, newCol))
area += 1
return area
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1 and (r, c) not in visited:
maxArea = max(maxArea, bfs(r, c))
return maxAreaTime: O(m·n) / Space: O(m·n)
Careful with one thing — this grid holds integers, not strings. I copy-pasted the == '1' condition from Number of Islands and every cell silently skipped. No error, just 0. Also decide where you count: at enqueue (start area at 1) or at dequeue (start at 0). Either works — mixing them double-counts.
994. Rotting Oranges
This is the problem that earns the pattern its keep. Two new ideas.
Multi-source BFS. Every rotten orange spreads at the same time — like a fire with multiple ignition points. So all of them enter the queue before the loop starts:
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1Levels are time. BFS visits cells in distance order, so processing the queue one level at a time turns distance into minutes. The snapshot loop is the key line:
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
fresh = 0
minute = 0
queue = collections.deque()
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
fresh += 1
elif grid[r][c] == 2:
queue.append((r, c))
if fresh == 0:
return 0
while queue and fresh > 0:
for _ in range(len(queue)): # ← snapshot: this minute only
row, col = queue.popleft()
for dr, dc in directions:
newR, newC = row + dr, col + dc
if (0 <= newR < rows and
0 <= newC < cols and
grid[newR][newC] == 1):
grid[newR][newC] = 2 # marking IS the visited set
fresh -= 1
queue.append((newR, newC))
minute += 1
return minute if fresh == 0 else -1Time: O(m·n) / Space: O(m·n)
Three details worth internalizing:
for _ in range(len(queue))takes the queue length before the level starts, so newly rotted oranges wait for the next minute. Without the snapshot, minutes bleed into each other.- There's no visited set — writing
2into the grid is the visited mark, because the enqueue condition checks== 1. If mutation isn't allowed, swap in a set; three lines change. - The
freshcounter answers "did everything rot?" without re-scanning the grid. Count up front, decrement per rot, check at the end. Still positive means some orange was walled off behind empty cells — that's the -1 case, and it's whyfresh > 0also sits in the while condition (otherwise a final do-nothing level inflates the count).
If a grid problem says "minimum time" or "shortest steps" — it's BFS. DFS can't guarantee distance order.
733. Flood Fill
The paint bucket tool. Easiest of the four, but it carries one trap that is the problem:
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
startColor = image[sr][sc]
if startColor == color: # ← the whole problem is this line
return image
rows, cols = len(image), len(image[0])
queue = collections.deque([(sr, sc)])
image[sr][sc] = color
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
while queue:
row, col = queue.popleft()
for dr, dc in directions:
newR, newC = row + dr, col + dc
if (0 <= newR < rows and
0 <= newC < cols and
image[newR][newC] == startColor):
image[newR][newC] = color
queue.append((newR, newC))
return imageTime: O(m·n) / Space: O(m·n)
Painting a cell is the visited mark — once painted, it no longer equals startColor, so it fails the enqueue condition forever. But if startColor == color, painting changes nothing, the "mark" never happens, and the BFS loops forever. Hence the early return.
DFS or BFS?
Both are O(m·n), so correctness-wise either works on the counting problems. The difference:
- Recursive DFS — shortest code, but recursion depth can hit O(m·n) on a snake-shaped island. On a 300×300 grid that's 90k frames, which can overflow the call stack.
- BFS — explicit queue on the heap, and for a grid the queue peaks at only O(min(m, n)).
In an interview either passes — mentioning the depth risk out loud is what separates "solved it" from "understands the tradeoff." And for the time-based problems like Rotting Oranges, it's not a choice: BFS only.
Summary
| Problem | What changes from the base skeleton |
|---|---|
| 200 Number of Islands | Nothing — this is the skeleton |
| 695 Max Area | BFS returns size; main loop keeps max |
| 994 Rotting Oranges | Multi-source start + level-per-minute snapshot + fresh counter |
| 733 Flood Fill | Painting = visited mark; startColor == color early return |
Three ways to block revisits showed up across these: a visited set (200, 695), overwriting the grid value (994), painting the color (733). Same job, different storage — if you're allowed to mutate the input, marking in place is free. Asking "may I mutate the input?" is itself a good interview signal.
Learn 200 cold, then the rest of the family is diff-tracking. Same trick works for the next pattern too.