Matrix Patterns
A matrix is usually just a graph or a dynamic programming table with two indices instead of one, and most matrix problems are a topic you already know applied to a grid. Island counting is a flood fill, minimum path sum is grid DP, and the shortest route through a maze is breadth-first search. What is genuinely specific to this topic is the index arithmetic: spiral boundaries, diagonal grouping, and rotating in place.
Where to start, and what comes next
- 01
Traversal Patterns
Spiral, diagonal and rotation. Pure index work, and the place where boundary handling is the entire difficulty.
- 02
Matrix Search
Two different search problems that look identical and are not, separated by how strongly the matrix is sorted.
- 03
Matrix DP & BFS
Grid DP and flood fill, which is where the graph and DP topics reappear on a grid.
If you only have time for three things
- Rotating in place as a transpose followed by a row reversal, which is two simple passes instead of one cycle-shuffling pass that is easy to get wrong.
- The staircase search from the top-right corner, and why that corner is the only viable start.
- Flood fill that sinks visited cells in place, trading the caller's input for O(1) extra space instead of a separate visited grid.
Confirm whether you may modify the input. Sinking cells in place is the neat solution to island counting and it destroys the grid, so asking first is both correct and a signal that you thought about it. On large grids, also be ready to say that a recursive flood fill can overflow the stack and that an explicit queue fixes it.
The idea underneath
For traversal: use direction arrays dx=[0,0,1,-1], dy=[1,-1,0,0]. For sorted matrix search, start from top-right corner. For grid DP, fill row by row. Current cell depends on top and left.
Problems that use these patterns
Questions people ask
Why does the staircase search start at the top-right?
Because it is the only corner where the two moves eliminate in opposite directions. Going left strictly decreases the value and going down strictly increases it, so each comparison removes a whole row or column. From the top-left both moves increase, which tells you nothing.
What is the difference between the two matrix search problems?
One requires each row to begin above the previous row's end, which makes the whole matrix a single sorted sequence you can binary search as a flat array. The other only guarantees rows and columns are individually sorted, which is weaker and needs the staircase walk.
How do I get the diagonals?
Every cell on the same diagonal shares the same value of row plus column. That single fact is the entire indexing scheme, and there are m + n - 1 diagonals in total.