Matrix as a Graph
A 2D matrix is an implicit graph where each cell (r, c) is a node connected to its neighbors (up, down, left, right — 4-directional, or 8-directional including diagonals). All graph algorithms (BFS, DFS, Union-Find) apply directly. The key difference: you use a visited array or modify the matrix in-place instead of an explicit adjacency list.
DFS for Connected Regions
Number of Islands (LC 200): iterate every cell; when you find a 1, DFS to mark all connected land as visited (set to 0 or use a visited set), increment island count. Time O(m*n), space O(m*n) for recursion stack.
def num_islands(grid):
count = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == "1":
dfs(grid, r, c)
count += 1
return count
def dfs(grid, r, c):
if r = len(grid) or c = len(grid[0]) or grid[r][c] != "1":
return
grid[r][c] = "0"
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(grid, r+dr, c+dc)BFS for Shortest Path
BFS finds the shortest path in an unweighted grid. Use a deque. Process level by level — each level = one step. Track visited cells to avoid cycles.
01 Matrix (LC 542): find the distance from each cell to the nearest 0. Multi-source BFS: start BFS from all 0-cells simultaneously. Each 1-cell gets the distance from the nearest 0. O(m*n) time.
Rotting Oranges (LC 994): multi-source BFS from all rotten oranges; spread rot one minute at a time. Count total fresh oranges; decrement on rot. Return minutes elapsed (BFS levels), or -1 if fresh oranges remain.
Walls and Portals / 0-1 BFS
When edges have weights 0 or 1, use a deque (0-1 BFS). Moving to a 0-weight neighbor: push to front. Moving to a 1-weight neighbor: push to back. This achieves Dijkstra-like behavior in O(m*n) without a priority queue.
Matrix Search Without Extra Space
Search a 2D Matrix II (LC 240): start at top-right corner. If target current, move down (eliminates row). O(m+n). Exploits the property that each row and column is sorted.
Spiral Matrix (LC 54): maintain four boundaries (top, bottom, left, right). Traverse right, down, left, up in order; shrink each boundary after traversal. Stop when top > bottom or left > right.
Dynamic Programming on Matrix
Unique Paths (LC 62): dp[r][c] = dp[r-1][c] + dp[r][c-1]. Fill row by row. O(m*n) time, O(n) space (single row suffices).
Maximal Square (LC 221): dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1 when grid[r][c] == 1. Represents the side length of the largest square with its bottom-right corner at (r, c). O(m*n) time and space.
Complexity Summary
| Problem | Algorithm | Time | Space |
|---|---|---|---|
| Number of Islands | DFS/BFS | O(m*n) | O(m*n) |
| Shortest Path (unweighted) | BFS | O(m*n) | O(m*n) |
| 01 Matrix distance | Multi-source BFS | O(m*n) | O(m*n) |
| Search Sorted Matrix | Staircase search | O(m+n) | O(1) |
| Maximal Square | DP | O(m*n) | O(n) |
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Coinbase Interview Guide