Pattern 13 of 22
Matrix and Grid Pattern: Template + 216 LeetCode Problems
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells.
- Easy
- 32
- Medium
- 125
- Hard
- 59
- Time
- O(r · c)
What the matrix and grid pattern is
A grid is a graph that nobody bothered to build: each cell is a node and its neighbours are the adjacent cells, so DFS, BFS and union-find all apply unchanged once you write the neighbour loop as a list of offsets rather than four copied blocks. Flood fill — walk from a cell, claim everything connected to it, repeat from every unclaimed cell — is the shape behind counting islands, enclosing regions and colouring components. Marking visited cells in the grid itself, by overwriting them, saves the extra structure and is usually acceptable; when it is not, a set of coordinate tuples is the fallback. The bounds check belongs at the top of the recursive call rather than before it, so there is one copy of it instead of four. Rotation and spiral problems are a different sub-family: they are index arithmetic, and the reliable way through them is to name the boundaries explicitly — top, bottom, left, right — and shrink them, rather than trying to derive a closed-form index map under pressure.
When to use it
- Cells are connected to their neighbours and you need regions, components or reachability.
- The shortest path through a grid is wanted, which is BFS with four or eight offsets.
- The answer is a distance from the nearest of many sources — one multi-source BFS pass.
- The problem is index mechanics: rotate in place, traverse in spiral order, transpose.
The matrix and grid template in Python
The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 216 problems listed below.
def count_islands(grid):
rows, cols = len(grid), len(grid[0])
def sink(r, c):
if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "1":
return # one bounds check, not four
grid[r][c] = "0" # mark in place; no separate seen set
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
sink(r + dr, c + dc)
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
islands += 1
sink(r, c)
return islandsComplexity characteristics
- Time
- O(r · c)
- Auxiliary space
- O(r · c) worst case, O(1) when marking in place
Flood fill visits every cell at most once across all of its starting points, because a claimed cell is never re-entered — so counting islands is linear in the number of cells even though it launches a traversal from many of them. The space is the stack or queue, which can hold every cell on a grid that is one large region. Overwriting visited cells in the grid itself removes the separate seen structure entirely, at the cost of destroying the input.
Eyes only
Meet the matrix and grid problem you did not practise.
In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.
All 216 matrix and grid LeetCode problems
Every problem in the library the matrix and grid pattern applies to, grouped by LeetCode's own difficulty rating. 178 of the 216 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.
Related LeetCode topics
Easy (32)
Medium (125)
Hard (59)
Matrix and Grid pattern FAQ
What is the matrix and grid pattern?
A grid is a graph that nobody bothered to build: each cell is a node and its neighbours are the adjacent cells, so DFS, BFS and union-find all apply unchanged once you write the neighbour loop as a list of offsets rather than four copied blocks.
How many LeetCode problems use the matrix and grid pattern?
This page lists 216 LeetCode problems that the matrix and grid pattern applies to: 32 Easy, 125 Medium and 59 Hard. 178 of them carry a complete Python solution with complexity analysis.
What is the time complexity of the matrix and grid pattern?
O(r · c) time and O(r · c) worst case, O(1) when marking in place space. Flood fill visits every cell at most once across all of its starting points, because a claimed cell is never re-entered — so counting islands is linear in the number of cells even though it launches a traversal from many of them. The space is the stack or queue, which can hold every cell on a grid that is one large region. Overwriting visited cells in the grid itself removes the separate seen structure entirely, at the cost of destroying the input.
When should I use the matrix and grid pattern in an interview?
Cells are connected to their neighbours and you need regions, components or reachability. The shortest path through a grid is wanted, which is BFS with four or eight offsets.
Which matrix and grid problem should I start with?
LeetCode 422. Valid Word Square is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.
What patterns are related to matrix and grid?
Depth-First Search, Breadth-First Search, Union-Find, Dynamic Programming. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.
More ways in: all 22 patterns, the curated study lists, or the full problem list.