Almost every matrix interview question is one of five patterns wearing a different costume: in-place traversal and transformation, flood fill (grid as a graph), dynamic programming on a grid, BFS for shortest paths, and state-space search for games. Learn to classify the problem in the first 60 seconds and the rest is execution. This guide maps each pattern to the tell-tale signals in the prompt, the data structure you reach for, and concrete problems to drill.
Matrix questions are popular for a reason. A 2D array is compact to state, hard to bluff, and it forces you to handle index math, boundaries, and visited state under time pressure. It is a good idea to remember that a matrix is just a 2-dimensional array, and most questions involving one are either dynamic programming or graph traversal in disguise, where each cell is a node with up to four neighbors.
Pattern 1: Traversal and in-place transformation
The simplest bucket. You walk the grid in some order (row-major, column-major, diagonal, or spiral) and either read a value or mutate it. The signal: the prompt talks about the layout of the matrix itself rather than paths or connectivity.
Start with Find the Width of Columns of a Grid, a junior-level warmup where you scan each column and track the maximum string length of its integers. It is pure column-wise traversal, and it is a good gut check that you can index grid[row][col] without fumbling row/column order. Matrix Cells in Distance Order is a close cousin: you generate every coordinate and sort by Manhattan distance from a center cell, which tests whether you can enumerate a grid and reason about distance without overthinking it.
The trickier members of this family ask you to mutate in place with O(1) extra space. Set Matrix Zeroes is the canonical version: when a cell is 0, zero out its entire row and column, but do it without a separate copy of the matrix. The naive solution allocates row and column marker arrays; the in-place solution uses the first row and first column as those markers, plus two booleans for the first row/column themselves. Interviewers love this problem precisely because the O(1) space version separates candidates who memorized an answer from those who can reason about aliasing.
A useful trick worth having in your pocket: for anything that needs both horizontal and vertical checks (win conditions in Tic-Tac-Toe or Connect 4, for example), verify the rows, transpose the matrix, and reuse the exact same row logic for the columns.
Pattern 2: Flood fill, or the grid as a graph
The moment a prompt says "connected", "region", "island", or "4-directionally adjacent", you are doing graph traversal. Treat each cell as a node, its in-bounds neighbors as edges, and run DFS or BFS while marking visited cells so you do not revisit them.
Count Islands With Total Value Divisible by K is a clean modern take. An island is a group of 4-directionally connected positive integers, and you flood fill each island, sum its values, and count how many sums are divisible by k. The mechanics are identical to the classic Number of Islands: iterate over every cell, and when you hit an unvisited land cell, launch a DFS/BFS that consumes the whole component. The only twist is accumulating a value during the fill.
Two implementation notes that trip people up:
- Mark cells visited as you enqueue them, not as you dequeue them, or BFS can push the same cell multiple times.
- Use a direction array like
[(1,0),(-1,0),(0,1),(0,-1)]and a single bounds check helper. Hand-writing fourifblocks is where off-by-one bugs live.
Pattern 3: BFS for shortest paths and layered search
If the question asks for the fewest steps, minimum moves, or the shortest path through a grid, it is BFS, not DFS. BFS explores in layers, so the first time it reaches the target the distance is guaranteed minimal (assuming uniform edge cost).
K Highest Ranked Items Within a Price Range is a strong example of BFS with a twist. The grid encodes walls, empty cells, and priced items, and you BFS outward from the start so cells are discovered in increasing distance. Within each BFS layer you break ties by price, then by row, then by column, and collect up to k items. The lesson: BFS gives you the distance ordering for free, and you layer the tie-break rules on top rather than trying to sort the entire grid up front.
When edges are not uniform (weights, or a budget you spend to pass obstacles), you upgrade to Dijkstra or a state-augmented BFS. A well-known example that companies still ask is Shortest Path in a Grid with Obstacles Elimination, where the state is (row, col, obstacles_remaining) rather than just (row, col). This idea, adding a dimension to the visited set, is the bridge to the final pattern. Meta in particular leans on grid BFS variants; our Meta company breakdown shows how often these show up in the phone screen and onsite loops.
Pattern 4: Dynamic programming on a grid
When the answer at a cell depends on its neighbors' answers (usually up, left, and up-left), build a DP table the same size as the grid. The signal: you are asked for a maximum/minimum size, count of ways, or an optimal sub-shape.
Maximal Square is the textbook case. For a binary matrix, dp[i][j] is the side length of the largest all-ones square whose bottom-right corner is (i, j), and the recurrence is dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) when the cell is 1. That single min of three neighbors is one of the most reused patterns in grid DP; recognizing it instantly is worth more than memorizing the whole solution.
Largest Submatrix With Rearrangements stacks a preprocessing step on top of DP thinking. First compute, for each cell, the number of consecutive ones ending at that cell going upward (a column-height DP). Then, because columns can be reordered freely, sort each row's heights descending and, for each position, the best rectangle height times width is height * (index + 1). It rewards decomposing a hard problem into "compute heights, then greedily measure", which is a transferable habit.
A practical tip from watching thousands of mock sessions: candidates reach for full 2D DP tables when a rolling one-row array would do. State that optimization out loud even if you code the 2D version; it signals you know the space cost.
Pattern 5: State-space search and game theory
The hardest tier turns the grid into a search over game states. Cat and Mouse II is a staff-level example: a cat and a mouse move on a grid of walls, floors, and food, each with jump limits, and you determine whether the mouse can win with optimal play. The board alone is not the state; the state is (mouse_position, cat_position, whose_turn, moves_played), and you evaluate it with minimax plus memoization or a bottom-up game-theory BFS over terminal positions.
You will not see this in a 45-minute screen often, but the underlying skill, defining the full state and searching it, is exactly what Pattern 3's obstacle-elimination problem hinted at. If you can articulate why the naive (row, col) state is insufficient and what you add to make it correct, you are demonstrating the reasoning senior and staff loops are grading for. Google and Amazon both pull from this harder end of the pool; see the Google and Amazon breakdowns for the mix by round.
How to practice these efficiently
Do not grind 80 random matrix problems. Pick two from each pattern above and force yourself to say the pattern name and the state representation before writing a line of code. Most candidates we run through mock interviews can code flood fill but stumble on articulating visited-state and complexity, which is the part interviewers actually score. Practice narrating the O(m*n) time and space out loud until it is automatic.
FAQ
Are matrix questions considered easy or hard in interviews?
They span the full range. Matrix coding problems are known to be tough in interviews, with many rated medium or hard on LeetCode. The traversal problems are approachable, but grid DP and state-space search reach staff difficulty. Classify the pattern first so you calibrate your time budget correctly.
DFS or BFS for grid problems?
Use BFS when you need a shortest path or a layer-by-layer distance ordering, because the first arrival at the target is optimal. Use DFS (often recursive) when you just need to touch every cell in a connected region, like counting islands. Both are O(m*n); the choice is about what the question asks, not performance.
What is the most common matrix mistake candidates make?
Mixing up row and column indices, and forgetting to mark cells visited before enqueuing in BFS. A single direction array plus one bounds-check helper eliminates most index bugs. Always confirm your row/column convention with the interviewer before coding.
How do I get O(1) space on problems like Set Matrix Zeroes?
Reuse the grid itself to store metadata. In Set Matrix Zeroes, the first row and first column become your zero-markers, with two extra booleans tracking whether that first row and column should themselves be zeroed. It is the standard trick whenever a problem says "in place".