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) |
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the standard approach for matrix BFS/DFS problems?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Define the four directions: dirs = [(0,1),(0,-1),(1,0),(-1,0)]. For each step, validate bounds: 0 <= r < rows and 0 <= c < cols. Mark visited immediately on insertion (BFS) or on entry (DFS) to avoid processing the same cell multiple times. For BFS, use a deque; for DFS, use recursion or an explicit stack. The visited set can be a separate boolean matrix or in-place modification of the grid (set visited cells to a sentinel value like 0 or #). In-place modification avoids extra space but mutates the input — ask the interviewer if that is acceptable."
}
},
{
"@type": "Question",
"name": "How does multi-source BFS work for problems like Rotting Oranges?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Multi-source BFS starts from multiple nodes simultaneously, treating them all as distance 0. This finds the minimum distance from any source to every other cell. Algorithm: add all source cells to the queue with distance 0. Process level by level (each level = one time step). For Rotting Oranges: enqueue all rotten oranges (2s) initially. Each BFS step spreads rot to adjacent fresh oranges (1s), converting them to 2s and enqueuing them. Count fresh oranges at start; decrement on each infection. When queue is empty, if any fresh oranges remain, return -1 (unreachable). Otherwise return the number of BFS levels elapsed."
}
},
{
"@type": "Question",
"name": "How do you find the shortest path in a binary matrix (0-cells are passable)?",
"acceptedAnswer": {
"@type": "Answer",
"text": "BFS from (0,0) to (n-1,n-1). Move in 8 directions (including diagonals). Each cell can only be a 0 (passable) or 1 (blocked). Start BFS with ((0,0), distance=1). For each cell, add unvisited 0-neighbors with distance+1. Return the distance when (n-1,n-1) is reached, or -1 if queue empties. Mark cells visited on enqueue (not on dequeue) to avoid adding the same cell multiple times. Edge cases: if start or end is blocked, return -1 immediately. Time O(n^2), space O(n^2) for the queue."
}
},
{
"@type": "Question",
"name": "What is the staircase search for a sorted matrix?",
"acceptedAnswer": {
"@type": "Answer",
"text": "For a matrix where each row and column is sorted (Search a 2D Matrix II, LC 240): start at the top-right corner (row=0, col=n-1). At each step: if target == current, return true. If target current, move down (row++) — eliminates this row for all left columns since all values to the left are smaller. Continue until out of bounds. O(m+n) time, O(1) space. This works because of the sorted property: moving left decreases values, moving down increases values.”
}
},
{
“@type”: “Question”,
“name”: “How does the maximal square DP work?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “dp[r][c] = side length of the largest square of 1s with its bottom-right corner at (r,c). If grid[r][c] == 0, dp[r][c] = 0. If grid[r][c] == 1: dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1. Why: a square at (r,c) can only be as large as the smallest square formed by its top, left, and top-left neighbors. The minimum of the three determines the limiting dimension. The answer is max(dp[r][c])^2. For a single row or column, dp values are 0 or 1 (base cases). O(m*n) time, O(n) space (optimize by keeping only the current and previous row).”
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Coinbase Interview Guide