Graph BFS / DFS (Grids)

Flood-fill each unseen region once; count the floods.

Brute force: O((R·C)²) — re-explore regions from every cell
With the pattern: O(R·C) — each cell visited once
Extra space: O(R·C) — visited set / queue (or in-place marking)

In plain English

“Looking at a map of islands, you drop a bucket of paint on any unpainted patch of land. The paint spreads to every connected bit of land and stops at water. Count how many times you had to pick up a new bucket — that's the number of islands.”

Why it's fast

A grid is a graph where each cell links to its up/down/left/right neighbours. Brute force might re-explore the same land from many starting cells. Marking cells visited the moment you reach them guarantees each cell is processed once, so the whole scan is O(rows × cols). BFS additionally gives shortest distance in unweighted grids.

Spot it when the problem says…

2-D grid of '1's and '0's
number of islands / connected regions
shortest path in a maze / unweighted graph
spread over time (rotting, fire, infection)
flood fill / paint bucket
cells reachable from the border

Visualize

Number of islands — flood fill

Count groups of '1's connected up/down/left/right.

recursion stack (sink calls)

empty

01/52

Scan every cell. Each time we hit unvisited land, that's a new island — then sink all of it so it's never counted again.

Keys: ← → step · space play/pause

pythonline 9

1def num_islands(grid):2    rows, cols = len(grid), len(grid[0])3    def sink(r, c):4        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "1":5            return6        grid[r][c] = "#"            # mark visited7        for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):8            sink(r + dr, c + dc)9    count = 010    for r in range(rows):11        for c in range(cols):12            if grid[r][c] == "1":13                count += 114                sink(r, c)15    return count

variables

count: 0

How to apply it

01Scan every cell; when you find an unvisited target cell, start a traversal and bump the count.
02From that cell, BFS (queue) or DFS (stack/recursion) into the 4 neighbours that are in bounds and valid.
03Mark a cell visited when you push it, not when you pop it, to avoid duplicates.
04For shortest-time / distance problems, use multi-source BFS: seed the queue with all sources at once.

Variations you'll meet

Number of islands (flood fill)

The visualizer's example. Sinks visited land in place by flipping '1' to '0'.

python

def num_islands(grid: list[list[str]]) -> int:    R, C = len(grid), len(grid[0])    def sink(r: int, c: int) -> None:        stack = [(r, c)]        grid[r][c] = "0"        while stack:            r, c = stack.pop()            for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "1":                    grid[nr][nc] = "0"     # mark on push                    stack.append((nr, nc))    count = 0    for r in range(R):        for c in range(C):            if grid[r][c] == "1":                count += 1                sink(r, c)    return count

Multi-source BFS (Rotting Oranges)

Enqueue every rotten orange at time 0; each BFS level is one minute.

python

from collections import dequedef oranges_rotting(grid: list[list[int]]) -> int:    R, C = len(grid), len(grid[0])    q = deque((r, c) for r in range(R) for c in range(C) if grid[r][c] == 2)    fresh = sum(row.count(1) for row in grid)    minutes = 0    while q and fresh:        minutes += 1        for _ in range(len(q)):            r, c = q.popleft()            for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:                    grid[nr][nc] = 2                    fresh -= 1                    q.append((nr, nc))    return -1 if fresh else minutes

Reverse flood from the border

Surrounded Regions, Pacific Atlantic: start from the edges and mark what's reachable, instead of testing every cell.

Adjacency-list graphs

Same idea with graph[u] neighbours and a visited set (Clone Graph, Word Ladder).

Common mistakes

Marking visited on pop instead of push, so the same cell gets queued many times.
Bounds checks in the wrong order (grid[nr][nc] before 0 <= nr < R) — negative indices silently wrap in Python.
Recursive DFS on a 300×300 grid blowing the recursion limit — use an explicit stack.
Counting BFS minutes off by one (incrementing after the last level, or when no fresh oranges exist).

Practice ladder

Easy → hard. Tick them off as you go.

0/8 solved

Think you've got it?

Let the AI interviewer throw a Graph BFS / DFS (Grids) problem at you and grade how you explain it.

Mock interview