Grid and matrix problems are graph problems in disguise. Each cell is a node; adjacent cells (up, down, left, right) are connected by edges. Recognizing this transforms intimidating 2D problems into standard BFS/DFS graph traversals. Grid problems appear in approximately 15-20% of coding interviews. This guide covers the essential patterns with templates.
Grid as Implicit Graph
Every grid problem is a graph problem. Cell (i, j) is a node. Edges connect to adjacent cells: (i-1,j), (i+1,j), (i,j-1), (i,j+1). For diagonal movement problems, add 4 more neighbors. Boundary check: 0 <= row < rows and 0 <= col < cols. Visited tracking: either modify the grid in-place (mark visited cells with a special value) or use a separate visited set/array. In-place modification is space-efficient but modifies the input (clarify with the interviewer if this is acceptable). Template for 4-directional traversal: directions = [(0,1), (0,-1), (1,0), (-1,0)]. For each direction (dr, dc): new_row = row + dr, new_col = col + dc. Check bounds and visited status before processing. This template applies to every grid problem — only the processing logic changes.
Pattern 1: Island Counting (Connected Components)
Number of Islands: given a grid of “1” (land) and “0” (water), count the number of islands (connected groups of land cells). Algorithm: iterate through every cell. When you find an unvisited “1”, increment the island count and flood-fill (BFS or DFS) to mark all connected land cells as visited. The flood-fill explores all 4-directional neighbors that are “1” and marks them. Time: O(rows * cols). Each cell is visited at most once. Variations: (1) Max Area of Island — same traversal, but track the size of each island (count cells during flood-fill). Return the maximum. (2) Number of Distinct Islands — normalize each island shape (translate to origin) and use a set of shapes to count distinct ones. (3) Surrounded Regions — “O” cells on the border and connected to the border are NOT surrounded. Start DFS from all border “O” cells, mark them safe. Everything else is surrounded and converted to “X”. (4) Number of Enclaves — count land cells not reachable from the border. DFS from border land cells, mark reachable. Count unmarked land cells.
Pattern 2: Shortest Path in Grid (BFS)
BFS on a grid finds the shortest path (minimum steps) from source to target. Each step moves to an adjacent cell. BFS explores level by level: all cells at distance 1, then distance 2, etc. The first time the target is reached, that is the shortest path. Shortest Path in Binary Matrix: find the shortest path from (0,0) to (n-1,n-1) through cells with value 0. BFS with 8-directional movement. Initialize queue with (0,0, distance=1). For each cell, explore all 8 neighbors. First time we reach (n-1,n-1), return the distance. Time: O(N^2). Rotting Oranges: fresh oranges adjacent to rotten ones become rotten each minute. Find the minimum time for all oranges to rot. Multi-source BFS: start with ALL rotten oranges in the queue simultaneously (not one at a time). Each BFS level = 1 minute. When the queue is empty, check if any fresh oranges remain (if yes, return -1). The BFS level count is the answer. Walls and Gates: fill each empty room with the distance to its nearest gate. Multi-source BFS from all gates simultaneously. Each room is assigned the distance from the first gate BFS that reaches it.
Pattern 3: DFS with Backtracking on Grid
Word Search: given a grid of characters and a word, determine if the word exists by following adjacent cells. DFS with backtracking: at each cell, if the character matches the current word position, mark the cell as visited, recurse in 4 directions for the next character. If all characters matched, return true. If no direction works, unmark (backtrack) and return false. Time: O(N * M * 4^L) where L is the word length (worst case, but pruning makes it much faster). Word Search II: find all words from a dictionary in the grid. Optimize with a Trie: insert all dictionary words into a Trie. DFS from each cell. At each step, check if the current path exists as a prefix in the Trie. If not, prune (do not explore further). If a complete word is found, add to results. The Trie prunes the search space dramatically — you stop early when no dictionary word has the current prefix. Unique Paths: count paths from top-left to bottom-right moving only right or down. This is DP, not DFS: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Time: O(N*M). With obstacles: dp[i][j] = 0 if obstacle, else dp[i-1][j] + dp[i][j-1].
Pattern 4: Matrix Transformation
Some grid problems require transforming the entire matrix based on cell relationships. 01 Matrix: for each cell, find the distance to the nearest 0. Multi-source BFS from all 0 cells simultaneously. Each BFS level increments the distance. Cells with 1 are assigned the BFS level when first reached. Time: O(N*M). Pacific Atlantic Water Flow: find cells that can flow to both the Pacific (top/left edges) and Atlantic (bottom/right edges). Two BFS/DFS passes: (1) BFS from all Pacific edge cells — find cells reachable from Pacific. (2) BFS from all Atlantic edge cells. The intersection is the answer. Game of Life: update all cells simultaneously based on neighbor counts. Problem: updating a cell affects its neighbors computation. Solution: encode the transition in-place: 0->1 = 2, 1->0 = -1. First pass: compute transitions. Second pass: decode (2->1, -1->0). This allows reading the original state while writing the new state. Grid problems pattern recognition: “count connected groups” = island counting (DFS/BFS). “shortest path/distance” = BFS. “find if path exists following rules” = DFS with backtracking. “transform matrix based on neighbors” = multi-source BFS or two-pass technique.