Matrix and Grid

The pattern: A grid is a graph whose edges are implied by adjacency, so you never build an adjacency list - you compute a cell’s neighbours from its coordinates.

Why this matters in interviews: Grid problems look like a separate topic and are not. Once you see (r, c) as a node and (r+dr, c+dc) as its edges, half of them collapse into BFS and DFS you already know. The other half are index gymnastics - rotation, spiral order, using the matrix as its own scratch space - and those are pure practice.

When to Recognize It

• The input is a 2D array and the problem talks about neighbouring cells, regions, or reachability
• “Count the islands”, “flood fill”, “how many steps to reach”, “can you get from A to B”
• Something spreads over time: fire, rot, water, infection. That is multi-source BFS
• You are asked to transform the matrix in place, with O(1) extra space
• The traversal order is geometric rather than logical: spiral, diagonal, boundary-first
• Keywords: “rotate the image”, “set matrix zeroes”, “shortest path in a binary matrix”

How It Works

An adjacency list stores edges because a general graph has no rule for finding them. A grid does have a rule. The neighbours of (r, c) are (r, c) plus a small offset, every time, for every cell. So you keep the offsets in a list and loop over it.

flowchart LR
    C["cell r c"]:::service
    U["r-1 c"]:::data
    D["r+1 c"]:::data
    L["r c-1"]:::data
    R["r c+1"]:::data

    C -->|"dr -1 dc 0"| U
    C -->|"dr +1 dc 0"| D
    C -->|"dr 0 dc -1"| L
    C -->|"dr 0 dc +1"| R

    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

The direction array is the whole idiom:

DIRS4 = ((-1, 0), (1, 0), (0, -1), (0, 1))          # orthogonal only
DIRS8 = DIRS4 + ((-1, -1), (-1, 1), (1, -1), (1, 1))  # add the diagonals

def is_valid(r, c, rows, cols):
    return 0 <= r < rows and 0 <= c < cols

Four directions or eight is a question the problem statement answers, and it is worth answering out loud before you write the loop. Islands, rotting oranges and walls-and-gates are 4-directional. Game of Life, minesweeper and most “count the neighbours” problems are 8-directional. Shortest-path-in-binary-matrix is 8-directional, which is easy to miss because it reads like a normal grid BFS.

The is_valid helper earns its keep. Most grid bugs are a missing or late bounds check, and the helper makes the check a single named thing you either called or did not. Written inline, the condition is four comparisons joined by and, and the fourth one is the one you forget at 2am.
💡 Bounds first, value second. is_valid(r, c) and grid[r][c] == 1 is safe because and short-circuits. Flip the order and you index out of range on the edge cells.

Template Code

Counting islands is the canonical grid traversal: scan every cell, and when you hit unvisited land, flood fill the whole region so you never count it twice. The flood fill can be DFS or BFS - they visit the same cells in a different order, and for counting, order does not matter.

The interesting choice is how you record “visited”. A separate set or boolean matrix costs O(m·n) extra space and leaves the input alone. Overwriting the cell as you go costs nothing extra, which is what most accepted solutions do, but it destroys the caller’s data. That is a real tradeoff, not a style preference: if the grid is read again after your call, including by your own second pass, in-place marking silently corrupts the answer.

Code

from collections import deque

DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))   # up, down, left, right

def num_islands(grid):
    """Count 4-connected regions of '1'. Sinks each island as it is found."""
    rows, cols = len(grid), len(grid[0])
    is_valid = lambda r, c: 0 <= r < rows and 0 <= c < cols

    def sink(r, c):
        # Bounds test first - short-circuit protects the lookup beside it
        if not is_valid(r, c) or grid[r][c] != '1':
            return
        grid[r][c] = '0'            # mark visited BEFORE recursing
        for dr, dc in DIRS:
            sink(r + dr, c + dc)

    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                sink(r, c)          # one call swallows the whole island
                islands += 1
    return islands

def sink_bfs(grid, start_r, start_c):
    """Same flood fill with a queue. No recursion depth to worry about."""
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start_r, start_c)])
    grid[start_r][start_c] = '0'
    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                grid[nr][nc] = '0'  # mark on enqueue, never on dequeue
                queue.append((nr, nc))

static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

boolean isValid(char[][] grid, int r, int c) {
    return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length;
}

int numIslands(char[][] grid) {
    int islands = 0;
    for (int r = 0; r < grid.length; r++)
        for (int c = 0; c < grid[0].length; c++)
            if (grid[r][c] == '1') { sink(grid, r, c); islands++; }
    return islands;
}

void sink(char[][] grid, int r, int c) {
    if (!isValid(grid, r, c) || grid[r][c] != '1') return;
    grid[r][c] = '0';                       // mark visited BEFORE recursing
    for (int[] d : DIRS) sink(grid, r + d[0], c + d[1]);
}

void sinkBfs(char[][] grid, int startR, int startC) {
    Deque<int[]> queue = new ArrayDeque<>();
    queue.add(new int[]{startR, startC});
    grid[startR][startC] = '0';
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        for (int[] d : DIRS) {
            int nr = cell[0] + d[0], nc = cell[1] + d[1];
            if (!isValid(grid, nr, nc) || grid[nr][nc] != '1') continue;
            grid[nr][nc] = '0';             // mark on enqueue
            queue.add(new int[]{nr, nc});
        }
    }
}

const int DIRS[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

bool isValid(vector<vector<char>>& g, int r, int c) {
    return r >= 0 && r < (int)g.size() && c >= 0 && c < (int)g[0].size();
}

void sink(vector<vector<char>>& g, int r, int c) {
    if (!isValid(g, r, c) || g[r][c] != '1') return;
    g[r][c] = '0';                          // mark visited BEFORE recursing
    for (auto& d : DIRS) sink(g, r + d[0], c + d[1]);
}

int numIslands(vector<vector<char>>& g) {
    int islands = 0;
    for (int r = 0; r < (int)g.size(); r++)
        for (int c = 0; c < (int)g[0].size(); c++)
            if (g[r][c] == '1') { sink(g, r, c); islands++; }
    return islands;
}

void sinkBfs(vector<vector<char>>& g, int startR, int startC) {
    queue<pair<int, int>> q;
    q.push({startR, startC});
    g[startR][startC] = '0';
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        for (auto& d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (!isValid(g, nr, nc) || g[nr][nc] != '1') continue;
            g[nr][nc] = '0';                // mark on enqueue
            q.push({nr, nc});
        }
    }
}

const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];

function numIslands(grid) {
    const rows = grid.length, cols = grid[0].length;
    const isValid = (r, c) => r >= 0 && r < rows && c >= 0 && c < cols;

    function sink(r, c) {
        if (!isValid(r, c) || grid[r][c] !== '1') return;
        grid[r][c] = '0';                   // mark visited BEFORE recursing
        for (const [dr, dc] of DIRS) sink(r + dr, c + dc);
    }

    let islands = 0;
    for (let r = 0; r < rows; r++)
        for (let c = 0; c < cols; c++)
            if (grid[r][c] === '1') { sink(r, c); islands++; }
    return islands;
}

function sinkBfs(grid, startR, startC) {
    const rows = grid.length, cols = grid[0].length;
    const queue = [[startR, startC]];
    grid[startR][startC] = '0';
    for (let i = 0; i < queue.length; i++) {   // cursor beats shift, O(1) pop
        const [r, c] = queue[i];
        for (const [dr, dc] of DIRS) {
            const nr = r + dr, nc = c + dc;
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (grid[nr][nc] !== '1') continue;
            grid[nr][nc] = '0';             // mark on enqueue
            queue.push([nr, nc]);
        }
    }
}

If you need the input intact, swap grid[r][c] = '0' for visited.add((r, c)) and add (r, c) not in visited to the guard. Everything else is identical. The cost is one extra structure sized O(m·n), which for interview-sized grids is free and for a 10000 x 10000 grid is 100 million entries, so the decision does eventually matter.

Variations

Multi-Source BFS

Rotting oranges: every minute, a rotten orange rots its four orthogonal neighbours. How many minutes until nothing fresh is left?

The trap is to read “spread from each rotten orange” as “run a BFS from each rotten orange”. That is k separate traversals, O(k · m · n), and you then have to take the minimum distance per cell and reconcile them. It is also the wrong mental model, because the oranges do not take turns.

Instead, push every source into the queue before the loop starts. BFS has one invariant: the queue holds cells in non-decreasing distance order. Seeding it with ten cells at distance 0 does not break that invariant, it just makes the first level ten cells wide. The frontier expands as a single wave, so the first time any cell is reached, it was reached by whichever source was nearest. One traversal, O(m · n), no reconciliation step. Draining len(queue) cells per outer iteration is what turns the traversal into a clock - one pass, one minute.

from collections import deque

def oranges_rotting(grid):
    """Minutes until no fresh orange remains, or -1 if one is unreachable."""
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))   # every rotten cell is a source at t = 0
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):    # snapshot the level, then drain it
            r, c = queue.popleft()
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1

    return -1 if fresh else minutes

The same shape solves walls-and-gates (seed all gates, fill distances), 01-matrix (seed all zeroes), and nearest-exit-from-maze (seed all exits, or seed the entrance and stop at the first exit). When you see “distance to the nearest X”, seed every X.

Rotate 90 Degrees in Place

Transpose-then-reverse is usually presented as a trick to memorise. It is not a trick, it is composition, and deriving it takes ten seconds at the whiteboard.

Work in coordinates. For an n x n matrix, a clockwise quarter turn must send the element at (r, c) to (c, n-1-r). Sanity-check a corner: (0, 0) is top-left, and clockwise it should land top-right at (0, n-1). The formula gives (0, n-1-0). Good. Now take the two operations you can do easily:

• Transpose reflects across the main diagonal: (r, c) → (c, r)
• Reverse each row mirrors horizontally: (r, c) → (r, n-1-c)

Compose them in that order. Transpose takes (r, c) to (c, r). Feed that into the row reversal and (c, r) becomes (c, n-1-r), which is the rotation exactly. Counter-clockwise is the mirror argument: transpose, then reverse each column, sending (c, r) to (n-1-c, r). Swap “rows” for “columns” and the other direction is free.

One detail is easy to get wrong. The transpose loop must cover the upper triangle only, with c running from r+1. Loop over the full square and every pair gets swapped twice, which is the identity, and you will stare at an unchanged matrix wondering where the bug is.

Code

def rotate(matrix):
    """Rotate an n x n matrix 90 degrees clockwise, in place."""
    n = len(matrix)
    for r in range(n):                      # transpose: upper triangle only
        for c in range(r + 1, n):
            matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
    for row in matrix:                      # then mirror each row
        row.reverse()

void rotate(int[][] m) {
    int n = m.length;
    for (int r = 0; r < n; r++) {           // transpose: upper triangle only
        for (int c = r + 1; c < n; c++) {
            int tmp = m[r][c]; m[r][c] = m[c][r]; m[c][r] = tmp;
        }
    }
    for (int[] row : m) {                   // then mirror each row
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            int tmp = row[i]; row[i] = row[j]; row[j] = tmp;
        }
    }
}

void rotate(vector<vector<int>>& m) {
    int n = m.size();
    for (int r = 0; r < n; r++)             // transpose: upper triangle only
        for (int c = r + 1; c < n; c++)
            swap(m[r][c], m[c][r]);
    for (auto& row : m)                     // then mirror each row
        reverse(row.begin(), row.end());
}

function rotate(m) {
    const n = m.length;
    for (let r = 0; r < n; r++) {           // transpose: upper triangle only
        for (let c = r + 1; c < n; c++) {
            [m[r][c], m[c][r]] = [m[c][r], m[r][c]];
        }
    }
    for (const row of m) row.reverse();     // then mirror each row
}

Spiral Traversal

Four boundaries - top, bottom, left, right - and you peel one edge at a time, shrinking the boundary you just consumed. The loop runs while top <= bottom and left <= right.

The bug everybody writes once is in non-square matrices. After walking the top row and the right column, the rectangle may have collapsed to nothing, and walking the bottom row would re-emit cells you already emitted. So the third and fourth edges need their own guards: check top <= bottom again before the bottom row, and left <= right again before the left column. A single 1 x n or n x 1 matrix is the test case that catches it.

Code

def spiral_order(matrix):
    if not matrix or not matrix[0]:
        return []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    out = []
    while top <= bottom and left <= right:
        for c in range(left, right + 1):          # top row, left to right
            out.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):          # right column, top down
            out.append(matrix[r][right])
        right -= 1
        if top <= bottom:                         # bottom row may be gone
            for c in range(right, left - 1, -1):
                out.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:                         # left column may be gone
            for r in range(bottom, top - 1, -1):
                out.append(matrix[r][left])
            left += 1

    return out

List<Integer> spiralOrder(int[][] m) {
    List<Integer> out = new ArrayList<>();
    if (m.length == 0 || m[0].length == 0) return out;
    int top = 0, bottom = m.length - 1;
    int left = 0, right = m[0].length - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) out.add(m[top][c]);
        top++;
        for (int r = top; r <= bottom; r++) out.add(m[r][right]);
        right--;
        if (top <= bottom) {                      // bottom row may be gone
            for (int c = right; c >= left; c--) out.add(m[bottom][c]);
            bottom--;
        }
        if (left <= right) {                      // left column may be gone
            for (int r = bottom; r >= top; r--) out.add(m[r][left]);
            left++;
        }
    }
    return out;
}

vector<int> spiralOrder(vector<vector<int>>& m) {
    vector<int> out;
    if (m.empty() || m[0].empty()) return out;
    int top = 0, bottom = m.size() - 1;
    int left = 0, right = m[0].size() - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) out.push_back(m[top][c]);
        top++;
        for (int r = top; r <= bottom; r++) out.push_back(m[r][right]);
        right--;
        if (top <= bottom) {                      // bottom row may be gone
            for (int c = right; c >= left; c--) out.push_back(m[bottom][c]);
            bottom--;
        }
        if (left <= right) {                      // left column may be gone
            for (int r = bottom; r >= top; r--) out.push_back(m[r][left]);
            left++;
        }
    }
    return out;
}

function spiralOrder(m) {
    if (!m.length || !m[0].length) return [];
    let top = 0, bottom = m.length - 1;
    let left = 0, right = m[0].length - 1;
    const out = [];
    while (top <= bottom && left <= right) {
        for (let c = left; c <= right; c++) out.push(m[top][c]);
        top++;
        for (let r = top; r <= bottom; r++) out.push(m[r][right]);
        right--;
        if (top <= bottom) {                      // bottom row may be gone
            for (let c = right; c >= left; c--) out.push(m[bottom][c]);
            bottom--;
        }
        if (left <= right) {                      // left column may be gone
            for (let r = bottom; r >= top; r--) out.push(m[r][left]);
            left++;
        }
    }
    return out;
}

Using the Matrix as Its Own Storage

Set matrix zeroes: if matrix[r][c] is 0, zero its entire row and column. You cannot zero as you scan, because the zeroes you write are indistinguishable from the zeroes that were already there, and the whole matrix collapses. The obvious fix is two arrays, one of rows to clear and one of columns, costing O(m + n).

The O(1) version stores those two arrays inside the matrix, in row 0 and column 0. Those cells are going to be overwritten anyway if anything in their row or column is zero, so they are free real estate.

Two things make it work. First, matrix[0][0] would have to be both the row-0 marker and the column-0 marker, so column 0 gets a separate boolean instead. Second, the fill pass has to run bottom-right to top-left, so you read every marker before you overwrite it. Go top-left first and row 0 gets zeroed early, after which every column looks like it needs clearing.

def set_zeroes(matrix):
    """Zero the row and column of every zero. O(1) extra space."""
    rows, cols = len(matrix), len(matrix[0])
    first_col_has_zero = False

    for r in range(rows):
        if matrix[r][0] == 0:
            first_col_has_zero = True      # column 0 needs its own flag
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = 0           # mark this row
                matrix[0][c] = 0           # mark this column

    for r in range(rows - 1, -1, -1):      # backwards: read markers before
        for c in range(cols - 1, 0, -1):   # overwriting them
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0
        if first_col_has_zero:
            matrix[r][0] = 0

The same idea shows up as encoding two values in one cell (Game of Life stores the next state in a higher bit, then shifts everything down in a second pass) and as negating values to mark indices as seen. All of them trade readability for space, and all of them mutate the input, so they belong in the “if the interviewer asks for O(1) space” column rather than in your first answer.

When the Grid Is Really a Shortest-Path Problem

BFS gives shortest paths only because every edge costs the same 1. The first time BFS reaches a cell, it reached it in the fewest steps, and no later path can beat it. That is the entire justification, and it evaporates the moment cells have different costs.

If entering a cell has a weight - a toll, a height difference, a penalty for changing direction - a cheap long route can beat an expensive short one, so the first arrival is no longer the best arrival. You need Dijkstra: same grid, same direction array, but a min-heap keyed on accumulated cost instead of a queue, and you finalise a cell when you pop it rather than when you first see it.

Two special cases worth knowing. When the only weights are 0 and 1, a deque gives you Dijkstra’s behaviour at BFS’s cost - push 0-weight moves to the front, 1-weight moves to the back. And when the grid is a DAG because movement is restricted to right and down, skip the graph machinery entirely and use dynamic programming, which is why Minimum Path Sum is a DP problem and Path With Minimum Effort is not.

Complexity

For an m x n grid:

The O(m · n) space on traversal catches people out. “BFS is O(width)” is true, but the worst-case width of a grid region is O(m · n) - picture a single island that zigzags through every cell.

Common Mistakes

• Mutating the input when the caller still needs it. In-place marking is the default in accepted solutions and it is wrong whenever the grid is read again afterwards, including by your own second pass. Decide deliberately, and say so in the interview
• Marking visited on dequeue instead of enqueue. Mark the moment you push. Mark on pop and the same cell gets pushed once per neighbour that sees it, so the queue grows past O(m · n), and in dense grids the “BFS” degrades into something much worse
• Row and column index swaps. grid[c][r], or len(grid) where you wanted len(grid[0]). These pass on square test cases and fail on rectangular ones, so always test a 1 x 4 or 3 x 1 input
• Checking bounds after the access. grid[nr][nc] == 1 and is_valid(nr, nc) throws on the border. The guard goes first and relies on short-circuit evaluation
• Recursive DFS on a large grid in Python. The default recursion limit is 1000 frames, and a 1000 x 1000 single-region grid needs a million. Raising the limit mostly moves the failure from a RecursionError to a segfault. Use the BFS version
• Forgetting the double swap in transpose. Running c from 0 instead of r + 1 swaps every pair twice and leaves the matrix untouched

Practice Problems

Traversal and flood fill:

• Number of Islands — the baseline, do this one first
• Max Area of Island — flood fill that returns a size instead of a count
• Island Perimeter — no traversal needed at all, which is the lesson
• Surrounded Regions — start from the border and invert the question
• Making A Large Island — label regions first, then test each flip
• Word Search — DFS with backtracking, so you must unmark on the way out

Multi-source and shortest path:

• Rotting Oranges — the multi-source template
• Shortest Path in Binary Matrix — 8-directional, easy to miss
• Path With Minimum Effort — weighted, so BFS fails and Dijkstra works
• Minimum Cost to Make at Least One Valid Path in a Grid — the 0-1 BFS deque trick
• Longest Increasing Path in a Matrix — DFS plus memoisation

Index manipulation:

• Rotate Image and Spiral Matrix — the two from this page, verbatim
• Set Matrix Zeroes — do the O(m+n) version first, then the O(1) one
• Search a 2D Matrix — flatten the index and binary search

Key Takeaways

• A grid is a graph with implied edges. Direction array plus bounds check replaces the adjacency list, and every BFS or DFS template carries over unchanged
• Confirm 4 versus 8 directions from the problem statement before writing the loop, and keep bounds checking in one named helper
• In-place visited marking is free in space and destructive to the input. Both answers are defensible; an undeclared choice is not
• Multi-source BFS is one traversal with a wide level 0, not k traversals. Seed every source whenever the question says “nearest”
• Clockwise rotation is transpose then reverse each row, and you can derive that in ten seconds from (r, c) → (c, n-1-r) rather than memorising it
• Weighted cells break the BFS invariant. Reach for Dijkstra, or a 0-1 BFS deque when the weights are only 0 and 1