Matrix Interview Patterns

Matrix problems are a staple of technical interviews because they test your ability to translate spatial reasoning into precise array manipulation. Mastering a handful of core patterns will allow you to decompose seemingly complex 2D grid problems into manageable, solvable steps. This guide focuses on the patterns you will most frequently encounter: traversing matrices in non-linear ways, searching within them, transforming them in-place, and solving optimization problems across their cells.

Understanding Matrix Fundamentals

Before tackling patterns, you must be fluent in the fundamentals. A matrix is a two-dimensional array represented as grid[row][column]. Row-column indexing is zero-based, meaning the top-left cell is grid[0][0]. Effective problem-solving hinges on cleanly tracking your position and boundaries. You will often need to manage iteration boundaries using variables like top, bottom, left, and right for traversal patterns. For problems involving connected components, visited marking is critical to avoid infinite loops; you can use an auxiliary visited matrix or mutate the original grid if allowed, often by setting a cell to a sentinel value like '#' or 0.

Core Pattern 1: Spiral and Zigzag Traversal

Spiral traversal involves moving around the matrix's perimeter, then moving inward layer by layer. The standard algorithm defines four boundaries: top row, right column, bottom row, and left column. You traverse from left to right along the top boundary, top to bottom along the right, right to left along the bottom (if still within bounds), and bottom to top along the left (if still within bounds). After each "loop," you shrink the boundaries inward: top++, bottom--, left++, right--. The process continues until the boundaries cross. This pattern tests meticulous boundary management and is a classic for assessing off-by-one error avoidance. A related, simpler pattern is zigzag traversal, which moves row by row, alternating direction from left-to-right and right-to-left.

Example (Spiral Order): For a 3x3 matrix, the traversal order is first row (left->right), last column (top->bottom), last row (right->left), first column (bottom->top), finally the center cell.

Core Pattern 2: Searching in a Sorted Matrix

A sorted matrix has rows and columns that are independently sorted, often in ascending order. The most efficient search leverages this property. The standard technique starts at the top-right corner (or bottom-left). At any cell (r, c), you compare its value grid[r][c] with the target.

• If target == grid[r][c], you've found it.
• If target < grid[r][c], you can eliminate the entire current column because all elements below are larger. Move left (c--).
• If target > grid[r][c], you can eliminate the entire current row because all elements to the left are smaller. Move down (r++).

This runs in $O(m+n)$ time for an $m\times n$ matrix. The key insight is choosing a starting point that gives you a clear "decision branch"—moving in one direction always increases values and moving in the other always decreases them.

Core Pattern 3: In-Place Transformation and Rotation

A common in-place transformation is rotating a square matrix by 90 degrees clockwise. The brute-force method of using a new matrix is trivial. The in-place rotation pattern requires layering. For each layer (like the rings in a spiral), you rotate groups of four elements in a cycle. For a cell at position (i, j) in an $n\times n$ matrix, its four rotational positions are:

1. Original: (i, j)
2. 90° clockwise: (j, n-1-i)
3. 180°: (n-1-i, n-1-j)
4. 270°: (n-1-j, i)

You swap these four elements in place, typically for all cells in the top-left quadrant of the current layer. This pattern tests your ability to derive and manage index mapping without extra memory.

Core Pattern 4: Island Counting (Connected Components with BFS/DFS)

The "number of islands" problem is the archetype for connected components in a grid. An island is a group of connected '1's (land) horizontally or vertically, surrounded by '0's (water). The solution uses a graph search—either BFS (Breadth-First Search) or DFS (Depth-First Search)—to explore and mark all cells belonging to a single island.

The algorithm iterates through every cell. When it finds an unvisited '1', it increments the island count and initiates a BFS or DFS from that cell to visit all adjacent land cells, marking them as visited. BFS uses a queue to explore neighbors level-by-level, while DFS uses recursion or a stack to go as deep as possible first. The choice often depends on stack depth concerns; for very large grids, BFS might be safer to avoid recursion depth limits.

Core Pattern 5: Dynamic Programming on Grids

Many optimization problems on grids, like finding unique paths or minimum path sums, are solved with dynamic programming (DP). A DP grid dp[i][j] stores the optimal solution (e.g., number of ways, minimum cost) to reach cell (i, j). You build the solution from a starting point (often the top-left) using a recurrence relation.

For example, in "Unique Paths" where you can only move right or down from (0,0) to (m-1, n-1), the recurrence is: $$dp[i][j]=dp[i-1][j]+dp[i][j-1]$$ with the base cases dp[0][j] = 1 and dp[i][0] = 1 for the first row and column. The final answer is in dp[m-1][n-1]. This pattern requires identifying the subproblem (state), the recurrence relation (transition), and the base cases (initialization). For path-sum problems, the relation might involve taking a min() or max() of previous states plus the current cell's value.

Common Pitfalls

1. Off-by-One and Boundary Errors: In spiral traversal or rotation, incorrectly handling the final row/column of a layer is common. Always trace a small 2x2 or 3x3 example by hand to verify your loop conditions. A good check: after shrinking boundaries, ask if top <= bottom and left <= right before proceeding with the next inner traversal.

1. Modifying Input Without Permission: Some problems forbid modifying the input matrix. Using the grid itself for visited marking (e.g., changing '1' to '#' for islands) can disqualify your solution. Always clarify with the interviewer or, if in doubt, use a separate visited data structure.

1. Inefficient Search in a Sorted Matrix: A naive linear scan or applying binary search row-by-row yields $O(m\log n)$, which is suboptimal. Failing to recognize the sorted property and use the top-right/bottom-left walkthrough is a missed opportunity for the optimal $O(m+n)$ solution.

1. Overlooking Connected Component Directions: In island problems, connectivity is typically defined as 4-directional (up, down, left, right). Accidentally including diagonal neighbors will lead to an incorrect count. Clearly define your direction arrays: directions = [(0,1), (1,0), (0,-1), (-1,0)] for 4-way connectivity.

Summary

• Matrix problems rely on mastering row-column indexing, boundary tracking for traversals, and efficient visited marking for graph searches.
• Spiral traversal is solved by managing four moving boundaries, a pattern that generalizes to other layered operations.
• To search a sorted matrix, start at the top-right or bottom-left corner to leverage sort order and eliminate a row or column with each step.
• In-place rotation of a square matrix involves swapping groups of four cells in a cyclical pattern, working from the outer layers inward.
• Island counting uses BFS/DFS to find connected components; the core challenge is marking all cells in an island during a single search to avoid double-counting.
• Dynamic programming on grids uses a DP table where each cell's value is derived from adjacent cells, following a recurrence relation that builds up to the final answer.