Matrix and Simulation

Updated Nov 19, 2026 · 4 min read
On this page

    Some problems have no clever trick. A grid has to be rotated, walked in a spiral, or moved forward one step by fixed rules, and the whole difficulty is doing exactly what the statement says without an off-by-one. Interviewers like them because they show whether you can keep indices straight under pressure. The pattern is a handful of habits that make that reliable.

    Graph BFS and DFS covers grids as graphs (islands, shortest paths). This page covers grids as grids: walking, rotating and updating them in place.

    When to recognise it

    • Rotate, transpose, flip or spiral a matrix, often "in place".
    • "Simulate" or "apply these rules to every cell": Game of Life, a board game, a robot following commands.
    • Count rows, columns and diagonals to decide a winner on a board.
    • Text layout: fill lines up to a width, pad with spaces, align. The "grid" is the page.
    • No search, no optimum to find. If the statement reads like a rulebook, it is simulation.

    Habit 1: one direction list

    Write the neighbours once as a list of (row change, column change) pairs and loop over it. The bounds check then lives in one place instead of eight.

    The four direct neighbours of (r, c) and the four diagonals as (row change, column change) pairs, and the loop that visits them with a single bounds check.
    The four direct neighbours of (r, c) and the four diagonals as (row change, column change) pairs, and the loop that visits them with a single bounds check.
    DIRS4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    DIRS8 = DIRS4 + [(-1, -1), (-1, 1), (1, -1), (1, 1)]
    
    def live_neighbours(board, r, c):
        """Count live cells around (r, c); one bounds check for all eight directions."""
        R, C = len(board), len(board[0])
        count = 0
        for dr, dc in DIRS8:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C:
                count += board[nr][nc]
        return count

    Habit 2: walk by layers

    Spiral order, rotation and "print the border" all work ring by ring. Keep four boundaries (top, bottom, left, right), walk one ring, then move every boundary one step inward.

    A 5×5 grid coloured by ring: outer ring, middle ring, centre cell. Four boundaries start at the edges and move inward after each ring.
    A 5×5 grid coloured by ring: outer ring, middle ring, centre cell. Four boundaries start at the edges and move inward after each ring.
    def spiral(matrix):
        """Walk ring by ring with four boundaries that move inward."""
        out = []
        if not matrix:
            return out
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1
        while top <= bottom and left <= right:
            for c in range(left, right + 1):
                out.append(matrix[top][c])
            for r in range(top + 1, bottom + 1):
                out.append(matrix[r][right])
            if top < bottom:                       # a single row has no bottom edge
                for c in range(right - 1, left - 1, -1):
                    out.append(matrix[bottom][c])
            if left < right:                       # a single column has no left edge
                for r in range(bottom - 1, top, -1):
                    out.append(matrix[r][left])
            top, bottom, left, right = top + 1, bottom - 1, left + 1, right - 1
        return out

    The two if checks are the whole difficulty: without them a single leftover row or column is read twice.

    Habit 3: never read what you already overwrote

    In a simulation every cell's next state depends on the old state of its neighbours. Updating in place while you scan mixes old and new values. Either write into a fresh grid, or, when the follow-up asks for O(1) extra space, encode both states in one cell (for 0/1 boards: bit 0 is the old state, bit 1 the new one) and shift at the end.

    def step(board):
        """One simulation step: read the old state, write a new grid."""
        R, C = len(board), len(board[0])
        nxt = [[0] * C for _ in range(R)]
        for r in range(R):
            for c in range(C):
                n = live_neighbours(board, r, c)
                nxt[r][c] = 1 if n == 3 or (n == 2 and board[r][c]) else 0
        return nxt

    Habit 4: decompose a transform

    A 90° clockwise rotation is a transpose followed by reversing each row. Counter-clockwise is a transpose followed by reversing each column. Breaking a transform into two simple passes is easier to get right than moving four cells at a time.

    def rotate(m):
        """Rotate a square matrix 90 degrees clockwise in place: transpose, then reverse each row."""
        n = len(m)
        for i in range(n):
            for j in range(i + 1, n):          # only above the diagonal, or every pair swaps back
                m[i][j], m[j][i] = m[j][i], m[i][j]
        for row in m:
            row.reverse()

    Common bugs

    • Rows and columns swapped: R = len(m), C = len(m[0]), and m[r][c] is row first. Test on a non-square input.
    • Reading a cell you already changed in a simulation step (habit 3).
    • Double-visiting the last row or column in a spiral (habit 2).
    • Swapping every (i, j) in a transpose, which swaps each pair twice and changes nothing.
    • Empty input: [] or [[]] crash on len(m[0]).

    Say this in the interview

    • "There's no trick here, so I'll keep the code boring: one list of directions, one bounds check."
    • "Every cell's next state depends on the old board, so I'll write into a new grid first, then show how to do it in place with a second bit."
    • "I'll test on a 1×n and an n×1 input, because that's where spiral and layer code breaks."

    Problems for this pattern

    1. Rotate Image: transpose, then reverse each row.
    2. Spiral Matrix: four boundaries that move inward.
    3. Game of Life: a direction list plus two states in one cell.
    4. Text Justification: fill each line greedily, then spread the spaces.

    Related

    Arrays and Strings · Graph BFS and DFS (grids as graphs) · Data Structure Design (board games as classes)