Grids as Graphs

The most common graph problem does not mention graphs. It hands you a 2D grid of characters or numbers and asks how many islands there are, or how many minutes until every orange rots, or the shortest path through a maze. All of those are the BFS and DFS from Traversal with one substitution: the neighbour function.

This page is that substitution, plus the traps that are specific to grids and do not exist on an adjacency list.

A grid is an adjacency list you never build.

Cell (r, c) is a vertex; its neighbours are the cells one step away. You do not store the edges because you can compute them - which means a 1000x1000 grid is a million-vertex graph that costs no memory beyond the grid itself.

1. The implicit edges

The centre cell has degree 4, an edge cell degree 3, a corner degree 2 - the corners are where off-by-one bounds bugs surface first.

An R x C grid graph has R * C vertices and 2*R*C - R - C edges - so both are O(R * C), and every traversal on it is O(R * C). There is no separate E to worry about: on a grid, E is a constant multiple of V, which is why grid problems are always linear in the cell count.

2. The neighbour function

The whole substitution is one list of offsets and one bounds check.

DIRS4 = ((-1, 0), (1, 0), (0, -1), (0, 1)) # up, down, left, right

 

def neighbours(grid, r, c, dirs=DIRS4):

rows, cols = len(grid), len(grid[0])

for dr, dc in dirs:

nr, nc = r + dr, c + dc

if 0 <= nr < rows and 0 <= nc < cols: # bounds FIRST

yield nr, nc

Using the wrong set merges islands that should be separate, or splits ones that should be joined.

⚠

Check bounds before reading the cell

Check bounds before reading the cell, never after. Writing if grid[nr][nc] == 1 and 0 <= nr < rows evaluates the index first. In Python that does not even crash reliably - grid[-1] is the last row, so a step off the top edge silently wraps to the bottom and your island count comes out wrong with no error at all. This is the single most common grid bug, and Python's negative indexing is what makes it silent rather than loud.

⚠

len(grid[0]) assumes a non-empty grid

len(grid[0]) assumes a non-empty grid. An input of [] throws IndexError before the traversal even starts. Problems that guarantee 1 <= m, n make this safe; problems that say "possibly empty" do not, and the guard is one line: if not grid or not grid[0]: return 0.

3. Marking visited: in place, or a set

A grid gives you a place to store visited for free - the grid itself.

Approach	Cost	When it is wrong
Mutate the grid - overwrite a visited land cell with water	O(1) extra space	The caller needs the input intact afterwards, or the problem runs several passes over the original.
A sentinel value - write 2 or # rather than a real value	O(1) extra space	The sentinel collides with a legal value. Writing '0' into a grid whose cells are already '0'/'1' is fine; writing 2 into a grid of arbitrary integers is not.
**A visited set of (r, c) tuples**	O(R * C) extra space	Never wrong. Slower by a constant factor and more memory, but it is the safe default and the only option on a read-only input.
A parallel boolean grid	O(R * C) extra space	Never wrong, and faster than a set of tuples. The right choice when you must not touch the input.

⚠

Mutating the input grid breaks the next read

Mutating the input is the fastest option and the one most likely to break the next thing you write. It is correct and idiomatic for single-pass problems like counting islands. It is a bug the moment the problem needs a second pass - "count islands, then find the largest one you could create by flipping one water cell" reads the original grid twice, and the first pass has already destroyed it. Decide which you need before writing the traversal, not after.

4. Flood fill: connected components on a grid

Counting islands is connected components with the grid neighbour function. The two-loop structure is identical: an outer scan finds unvisited land, an inner traversal floods the whole island.

def count_islands(grid):

if not grid or not grid[0]:

return 0

rows, cols = len(grid), len(grid[0])

 

def flood(r, c):

stack = [(r, c)]

grid[r][c] = '0' # mark on PUSH, before the loop

while stack:

cr, cc = stack.pop()

for nr, nc in neighbours(grid, cr, cc):

if grid[nr][nc] == '1':

grid[nr][nc] = '0' # mark on push, not on pop

stack.append((nr, nc))

 

count = 0

for r in range(rows):

for c in range(cols):

if grid[r][c] == '1': # OUTER: fresh dry land

count += 1

flood(r, c) # INNER: sink this whole island

return count

Mnemonic

Outer loop counts islands; inner traversal sinks one. count += 1 belongs in the outer loop and nowhere else - putting it inside the flood counts cells, which is the area, not the island count. Both are real problems (LC 200 vs LC 695), and they differ by exactly where that line sits.

⚠

Recursive flood fill overflows the stack

Recursive flood fill on a large grid overflows the stack. A 1000x1000 grid that is entirely land is a single component of a million cells, and recursive DFS needs a million frames - Python dies at about a thousand. Iterative DFS with an explicit stack, or BFS with a queue, has no such limit. This is not a theoretical concern; it is the standard failure mode on grid problems with large constraints.

5. Multi-source and border-seeded traversals

Two seeding patterns cover most of the grid problems that are not plain component counting.

Multi-source - seed every starting cell at distance 0 and the layers measure distance to the nearest source. Rotting oranges, 01-matrix, walls-and-gates are all this. The mechanics are on Traversal; on a grid the only difference is that you find the sources with a full scan first.

Border-seeded - the inversion that makes several problems easy. When a problem asks about regions that do not touch the edge (surrounded regions, closed islands, enclaves), do not try to detect "surrounded" directly. Flood inward from the border to mark everything that escapes, then whatever is left unmarked is surrounded by definition.

def solve_surrounded_regions(board):

if not board or not board[0]:

return

rows, cols = len(board), len(board[0])

 

def escape(r, c):

stack = [(r, c)]

board[r][c] = 'E' # E = reaches the border

while stack:

cr, cc = stack.pop()

for nr, nc in neighbours(board, cr, cc):

if board[nr][nc] == 'O':

board[nr][nc] = 'E'

stack.append((nr, nc))

 

for r in range(rows): # seed the left and right edges

for c in (0, cols - 1):

if board[r][c] == 'O':

escape(r, c)

for c in range(cols): # seed the top and bottom edges

for r in (0, rows - 1):

if board[r][c] == 'O':

escape(r, c)

 

for r in range(rows):

for c in range(cols):

board[r][c] = 'O' if board[r][c] == 'E' else 'X'

Mnemonic

"Cannot escape" is hard to test; "can escape" is one traversal. Whenever a grid problem defines a region by what it is not adjacent to, flip the question and seed from the boundary. Surrounded regions, closed islands, number of enclaves, and Pacific-Atlantic water flow are all the same move - the last one just runs it twice, once from each pair of edges, and intersects.

⚠

Seeding grid borders needs all four edges

Seeding the border needs all four edges, and the corners must not be double-counted or missed. The two loops above cover left/right columns then top/bottom rows, which visits each corner twice - harmless, because the second visit finds an already-marked cell. Writing a single loop over range(max(rows, cols)) to save a line is how corners get skipped on non-square grids.

6. When a grid needs more than BFS

The neighbour function is not the only knob. Three escalations, each with a clear tell in the problem statement:

The problem says	The grid is really	Reach for
every step costs 1 (or is free)	an unweighted graph	BFS - O(R * C)
each cell has a cost/height/effort to enter	a weighted graph	Dijkstra with (cost, r, c) in the heap (Shortest Paths)
a step is free along a path and costs 1 to turn or break a wall	a 0-1 weighted graph	0-1 BFS with a deque (Traversal)
"you may remove up to k obstacles", "you have collected these keys", "you are facing this direction"	a layered graph: one copy of the grid per state	BFS over (r, c, state) - the state joins the visited key
minimise the maximum single step (swim/effort)	a bottleneck-path problem	Dijkstra with max instead of +, or binary search plus a plain BFS

⚠

Extra state must live in the visited key

When the state is more than (r, c), the visited key must include it. "Shortest path with at most k obstacles removed" has (r, c, used) as its vertex, and marking only (r, c) visited makes the search reject a route that arrives later but with obstacles to spare - a wrong answer, not a slow one. The rule: visited holds whatever fully identifies a vertex, and if you added a dimension to the state, you added it to the key.

A layered grid is k + 1 stacked copies of the grid.

Moving normally keeps you on your layer; spending a resource drops you to the next one down. Once you see it that way there is no new algorithm - it is plain BFS on a graph that happens to be R * C * (k+1) vertices, and the complexity is exactly that.

Where to go next

• Traversal - the general form of this page: any problem with states and legal moves is a graph, grid or not.
• Matrix practice - the problem sets that use everything here.