Grid problems look like their own category, but almost all of them are graph problems where the graph is never built. A matrix of m rows and n columns is a graph with m·n nodes; each cell (r, c) has up to four neighbours — (r-1, c), (r+1, c), (r, c-1), (r, c+1) — or eight if diagonals count. You never allocate adjacency lists: a small direction array plus a bounds check generates the neighbours on demand. That single observation lets you transfer everything you know about DFS and BFS directly onto 2D arrays.

What changes from problem to problem is only what you are asked about the graph: how many connected regions there are (DFS), how far something is (BFS), which cells can reach a border (search backwards from the border), or a fixed visiting order that is not a search at all (simulation with shrinking boundaries). The drills on this page cover each of those questions, in increasing order of subtlety.

Before writing a line of code, translate the question into graph language. The cause → effect chain below is the reasoning you should be able to say out loud in an interview; the decision diagram underneath maps each kind of question to the technique that answers it.

Four templates cover every drill on this page. Learn them as shapes: once you can write each one from memory in under two minutes, the drills reduce to choosing a template and deciding what "visited" and "neighbour" mean.

grid dfs in-place

An image is a 2D array of integers (pixel colours). Starting from pixel (sr, sc), recolour that pixel and every pixel connected to it 4-directionally that has the same original colour to the new color. Return the modified image. This is the paint-bucket tool from any drawing program.

A brute-force idea is to repeatedly sweep the whole image, painting any original-coloured pixel adjacent to a painted one, until a sweep changes nothing — O((m·n)²) in the worst case (a long snake-shaped region gains one pixel per sweep). DFS from the start pixel paints the region directly: every pixel is painted at most once and each paint examines four neighbours, so the work is proportional to the image size. BFS works equally well; DFS is simply shorter to write.

• Remember original = image[sr][sc]. If it already equals color, return immediately.
• Call dfs(sr, sc): return if out of bounds or the pixel is not original.
• Paint the pixel color (this is also the visited mark).
• Recurse down, up, right, left.

grid dfs connected components

Given an m × n grid of characters where '1' is land and '0' is water, return the number of islands. An island is a maximal group of land cells connected horizontally or vertically; the grid is surrounded by water.

A naive approach labels each land cell by checking whether it can reach any previously labelled cell — a search per cell, O((m·n)²). Instead, scan once; on finding unvisited land, increment the counter and flood-fill the island so it can never be counted again. Each cell is visited by the scan once and sunk at most once. Union-Find also works (union each land cell with its right and down land neighbours, count roots) and is useful if cells arrive online, but DFS is the cleanest for a static grid.

• Scan rows top to bottom, columns left to right.
• On '1': count++, then sink(r, c).
• sink returns on out-of-bounds or non-'1'; otherwise sets '0' and recurses in four directions.
• Return count.

grid dfs post-order sum

Given a binary matrix grid of 0 (water) and 1 (land), an island is a 4-directionally connected group of 1s. Return the area (number of cells) of the largest island, or 0 if there is no land.

You could run Number of Islands and then do a second pass counting cells per island label, but that needs a label array and two passes. Folding the count into the DFS return value is a single pass with no extra structure. A BFS alternative counts the cells it polls from the queue; same O(m·n).

• Scan every cell; on land, compute area(r, c) and update best.
• area returns 0 for out-of-bounds / water / visited.
• Otherwise sink the cell and return 1 + the four recursive areas.

grid bfs multi-source simulation

Each cell is 0 (empty), 1 (fresh orange) or 2 (rotten orange). Every minute, each fresh orange 4-directionally adjacent to a rotten one becomes rotten. Return the minimum number of minutes until no fresh orange remains, or -1 if some fresh orange can never rot.

A direct simulation copies the grid every minute and rots neighbours of rotten cells until nothing changes — O((m·n)²) because there can be m·n minutes of O(m·n) scans. Multi-source BFS touches each cell once: enqueue every initially rotten orange, count the fresh ones, then process the queue level by level, decrementing fresh each time an orange rots. When the queue empties, fresh == 0 means success.

• Enqueue all 2s; count all 1s into fresh.
• While the queue is non-empty and fresh > 0: process exactly queue.size() cells (one minute), rotting fresh neighbours as they are enqueued; then minutes++.
• Return minutes if fresh == 0, else -1.

grid bfs shortest path 8-directional

Given an n × n binary matrix, return the length of the shortest clear path from the top-left cell to the bottom-right cell, or -1 if none exists. A clear path visits only 0 cells, and consecutive cells may be connected in any of the 8 directions (edges or corners). The length is the number of cells visited, including both ends.

DFS that tries every path and keeps the minimum is exponential (the number of simple paths in a grid explodes). Dijkstra would work but its priority queue is unnecessary when every edge weight is 1 — a FIFO queue already pops nodes in non-decreasing distance order. BFS by levels returns the level number the moment the goal is polled.

• If the start or the goal is blocked, return -1 immediately.
• Enqueue (0,0), mark it seen, length = 1.
• Process level by level; return length when (n-1, n-1) is polled.
• For each of 8 neighbours that is inside, open and unseen: mark seen, enqueue.
• After each level, length++. If the queue empties, return -1.

grid dfs reverse search two passes

An m × n island has a height per cell. The Pacific Ocean touches the top and left edges; the Atlantic touches the bottom and right edges. Rain water flows from a cell to a 4-directional neighbour whose height is less than or equal to its own. Return every cell from which water can reach both oceans.

Brute force runs a DFS from every cell, following downhill moves, to see whether it reaches both oceans — O(m·n) per cell, O((m·n)²) total, with no reuse between overlapping searches. The reverse formulation shares work: each map is filled by one multi-source DFS that visits every cell at most once, so the whole algorithm is O(m·n).

• Create pacific[m][n] and atlantic[m][n].
• From every left-column and top-row cell, climb into pacific; from every right-column and bottom-row cell, climb into atlantic.
• climb(r, c): if already marked, return; mark; recurse into neighbours whose height is >= the current height.
• Collect cells marked in both maps.

matrix simulation boundaries

Given an m × n matrix, return all of its elements in spiral order: left-to-right along the top row, top-to-bottom down the right column, right-to-left along the bottom row, bottom-to-top up the left column, then repeat on the inner sub-matrix.

An alternative is a direction-turning walk with a visited matrix: move in the current direction and turn right when the next cell is out of bounds or visited. It is O(m·n) time but O(m·n) extra space. The boundary method needs only four integers. Both visit each element exactly once.

• Initialise top=0, bottom=m-1, left=0, right=n-1.
• While top <= bottom && left <= right: walk top row then top++; walk right column then right--.
• If top <= bottom: walk bottom row backwards then bottom--.
• If left <= right: walk left column upwards then left++.

Every drill on this page is O(m·n) time — the difference is which traversal and what you store per cell. If you can explain why each row in the table uses the technique it does, you have the chapter.

← 06 · Binary Trees & BST All Coding Drills 08 · Graphs →