Matrix and Grid Pattern: Template + 216 LeetCode Problems

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 islands

Complexity 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.

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 patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Matrix and Grid pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.