Grids as graphs

Problem

The input is a rectangular array of cells: land and water, walls and gates, fresh and rotten fruit, heights. You are asked how many connected regions there are, how big the largest is, how far each cell is from something, or which cells can reach somewhere. Moving is allowed between touching cells (four directions unless the statement says otherwise) and blocked by some cell values.

Intuition

Pour a bucket of paint on one square of a floor plan: it spreads to every touching square of the same kind and stops at walls. Flood fill is exactly that, and the paint is the visited mark. Everything you learned about graph search carries over, because "touching" is the only edge rule and the grid gives it for free.

Now pour paint on several squares at the same moment. Each drop spreads outward one ring per tick, and the first ring to reach a square is the nearest drop. That is multi-source BFS: put every source in the queue before the first step. The queue still holds nodes in nondecreasing distance, so the shortest-path argument for ordinary BFS still applies, with a virtual super-source joined to every source by an edge of length zero.

Scanning in reading order, each land cell that has no number yet starts a fill that numbers its whole island. Empty cells are water. The diagram scrolls sideways on a narrow screen.

Mechanics

Neighbors and bounds

Keep a tuple of direction offsets, ((1, 0), (-1, 0), (0, 1), (0, -1)), and for each cell test 0 <= nr < rows and 0 <= nc < cols before reading the neighbor. Eight-direction problems just use eight offsets. Cell (r, c) can be stored as a tuple or as the integer r * cols + c when you need a compact key.

Flood fill and visited marks

Visiting needs a mark so a cell is processed once. Either keep a separate seen set, or, when you may change the input, overwrite the cell (sink the island by writing water into it). The mark goes on when the cell is pushed, as in any graph search. The invariant is: a cell is marked exactly when it has been put on the frontier, and every marked cell has had all its in-bounds, same-kind neighbors marked or queued. When the frontier empties, the region is the set of marked cells, and none of its neighbors of the same kind remain unmarked.

Prefer an explicit stack or queue to recursion: a 300 × 300 grid of land is a path 90,000 deep, far past Python's default limit of about a thousand frames.

Multi-source BFS

Seed the queue with every source, each at distance 0, then run the ordinary loop. All cells at distance d leave the queue before any at d + 1, so a cell's recorded distance is its distance to the nearest source. One search of O(R·C) replaces a search from every cell, which would cost O((R·C)²). When time matters, as in "minutes until everything rots", process the queue one layer at a time and count the layers.

Reverse the search

"Which cells can flow to the ocean" asks about many starting cells and a few targets. Run the search from the targets over the reversed rule (water flows downhill, so search uphill). Two searches, one per ocean, intersect to the answer. The same trick solves "regions not touching the border": mark what touches the border, and everything else is the answer.

All the zeros start in the queue together, so each ring grows from the nearest one. The cell in the bottom-right corner is 3 steps from its nearest zero.

Worked example

Islands. The scan reaches cell (0,0) first and fills the 2 × 2 block, which is island 1 with area 4. The lone land cells at (1,3) and (2,2) touch only diagonally, so they are separate islands of area 1 each, and the pair in the last row is island 4 with area 2. Diagonal contact does not connect cells under the four-direction rule.

Perimeter. Every land cell contributes one edge for each side that faces water or the grid boundary: 22 in total. That count needs no search at all, only a pass over the cells, which is a reminder to check whether a grid problem needs a traversal in the first place.

Painting. Filling the region around cell (1,1) of 112 / 110 / 101 with colour 3 changes 5 cells and gives 332 / 330 / 301. Calling the fill with the colour already in place must return immediately, or it would loop forever; the helper checks that first.

Reverse flow. On a 4 × 4 height map, searching uphill from the Pacific edge (top and left) and from the Atlantic edge (bottom and right) reaches 13 and 8 cells; the 5 cells in both sets are (0, 3), (1, 3), (2, 2), (3, 0), (3, 1), written as (row, column).

Implementation

from collections import deque

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1":
                continue
            count += 1
            grid[r][c] = "0"
            stack = [(r, c)]
            while stack:
                cr, cc = stack.pop()
                for dr, dc in DIRS:
                    nr, nc = cr + dr, cc + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
                        grid[nr][nc] = "0"
                        stack.append((nr, nc))
    return count


def nearest_zero(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[-1] * cols for _ in range(rows)]
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))
    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
    return dist

Variations and edge cases

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 2)
    fresh = sum(row.count(1) for row in grid)
    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    return -1 if fresh else minutes


def solve_surrounded(board):
    rows, cols = len(board), len(board[0])
    stack = [(r, c) for r in range(rows) for c in range(cols)
             if (r in (0, rows - 1) or c in (0, cols - 1)) and board[r][c] == "O"]
    for r, c in stack:
        board[r][c] = "S"
    while stack:
        r, c = stack.pop()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "O":
                board[nr][nc] = "S"
                stack.append((nr, nc))
    for r in range(rows):
        for c in range(cols):
            board[r][c] = "O" if board[r][c] == "S" else "X"

• Mutating the input. Overwriting cells is shortest, but only if the caller does not need the grid afterwards. Otherwise keep a seen set of tuples.
• Counting layers. To count minutes, take len(queue) before each round and process exactly that many cells, as above. A fresh counter detects unreachable cells without a final scan.
• Seeding the queue. Sources must all be queued before the first pop. Seeding them lazily gives wrong distances.
• Different neighbor rules. Knight moves, eight directions, wrap-around edges and one-way doors change only the offsets or the test. Keep that rule in one place.
• Edge cases: an empty grid or an empty first row, a single cell, a grid with no sources (the distance table stays all -1), a start that is already the target, and rows of unequal length when the input is ragged.
• Backtracking on a grid (Word Search) is not a flood fill: the same cell may be reused on another path, so the mark is undone on the way back. See constraint backtracking.

Complexity and tradeoffs

• Time: O(R·C). Each cell is marked once and examines a constant number of neighbors (four or eight). Multi-source BFS is also O(R·C), not O(sources × R·C).
• Space: O(R·C) worst case for the frontier or the seen set; O(min(R, C)) for a BFS ring on a square-ish open grid. Marking in place removes the seen set.
• Baseline. Running a separate search from every cell to its nearest source is O((R·C)²). The shared queue is what removes the square.
• DFS or BFS. Regions, areas and border tests: either works, and an explicit stack is the simplest. Distances and "per minute" spreads need BFS.
• When it fails. Cells with different move costs need Dijkstra (Path With Minimum Effort, Swim in Rising Water). Repeated "add land, then count islands" queries suit union-find. Very large sparse grids should be stored as a set of occupied cells, not a full matrix.

Problems

Flood Fill, Number of Islands, Max Area of Island and Island Perimeter are the plain region questions. Surrounded Regions and Pacific Atlantic Water Flow reverse the question to start from the border. Rotting Oranges, 01 Matrix, Walls And Gates and Shortest Path to Get Food are multi-source or single-source BFS where the answer is a number of steps.

Easy

• 463. Island Perimeter NeetCode 250
  Every land cell adds four edges, minus two for each neighbouring pair of land cells.
• 733. Flood Fill Grind 169
  DFS or BFS from the start cell, recolouring connected cells with the original colour, and return early if the new colour is the same.

Medium

• 130. Surrounded Regions NeetCode 150 NeetCode 250
  Any region touching the border survives, so flood from the border first and then capture every O that flood never reached.
• 200. Number of Islands Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Each unvisited land cell starts a new island, and a flood fill from it marks the whole island visited.
• 286. Walls And Gates NeetCode 150 NeetCode 250
  Start one BFS from all gates at once, so each room is first reached by its nearest gate.
• 417. Pacific Atlantic Water Flow Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Search uphill from each ocean's border cells and return the cells both searches reach.
• 542. 01 Matrix Grind 169
  Start one BFS from every zero at once, and the first time a cell is reached gives its distance.
• 695. Max Area of Island NeetCode 150 NeetCode 250
  Flood fill from each unvisited land cell, counting cells as you go, and keep the largest count.
• 994. Rotting Oranges Grind 169 NeetCode 150 NeetCode 250
  Start a BFS from every rotten orange at once; the number of levels is the minutes, and any fresh orange left means -1.
• 1730. Shortest Path to Get Food Grind 169
  BFS from your position over open cells and stop at the first food cell reached.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 79. Word Search Medium
• 212. Word Search II Hard
• 329. Longest Increasing Path in a Matrix Hard

Connections

This is graph traversal with the adjacency list replaced by a neighbor rule, so cycles, visited marks and the BFS distance argument all carry over unchanged. Weighted grids move on to Dijkstra, and grid problems that ask for connectivity under changes use union-find.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 20 (breadth-first search and its shortest-path proof, which covers the super-source argument).
• Skiena, The Algorithm Design Manual, chapter 7 (graph traversal and connected components).
• Sedgewick and Wayne, Algorithms, section 4.1 (undirected graphs and implicit graphs).
• Foley, van Dam, Feiner and Hughes, Computer Graphics: Principles and Practice, the section on seed fill (the origin of flood fill, with the scanline variants used for large images).
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.