Skip to content
Hari KharelStudy

Grids and matrices

coreCommon atGoogleAmazonMetaMicrosoftUberRead firstArraysPractise in the Sandbox →

A grid is an array of rows; cell (r, c) is grid[r][c], and in flat row-major memory it’s index r * cols + c. Almost every grid problem is built from four pieces: a traversal order, direction vectors for neighbours, a bounds check, and sometimes an in-place transform like transpose. Visiting every cell costs O(rows × cols).

The idea in plain words

Section titled “The idea in plain words”

Think of a spreadsheet: rows going down, columns going across. Two numbers name every cell. The only question is the order you visit cells in, and which cells count as “next to” each other.

Three ideas carry you through most problems:

  • A grid is a graph in disguise. Each cell is a node; its up/down/left/right neighbours are its edges. Flood fill, shortest path and connected regions are just BFS and DFS with a neighbour function.
  • Direction vectors replace four copy-pasted ifs: loop over [(-1,0), (1,0), (0,-1), (0,1)] (add the four diagonals for 8-neighbour problems).
  • Boundaries as variables. Spiral order, layer-by-layer rotation and “peel the onion” problems keep top, bottom, left, right and shrink them.

See it

Section titled “See it”

Pick a traversal order and step through it. The numbers are the visit order; the chips show the flat index. Spiral mode shades the bounds that are still unvisited, so you can see why the guards matter on non-square grids (try 2×5 or 5×1).

Walking a grid
step through
cell—
flat index r·cols+c—
visited0
currentvisited (number = visit order)inside current bounds
A 4×5 grid. Row-major memory puts cell (r, c) at flat index r·cols + c.
1 / 22

When to reach for it

Section titled “When to reach for it”
The problem says… What to use
“board”, “map”, “image”, “maze”, “seats”, any 2-D layout A grid with a neighbour function.
“connected region”, “flood fill”, “how many areas” DFS/BFS over cells, a visited set (or overwrite cells in place). See union-find for regions that grow over time.
“fewest moves from A to B” BFS from A over cells.
“rotate”, “transpose”, “mirror” an image Index mapping; in-place via swaps.
“spiral”, “diagonal”, “zig-zag” order Boundary variables or r + c / r − c diagonal keys.
“sum of a sub-rectangle”, many times 2-D prefix sums.
“each cell depends on the cell above/left” 2-D dynamic programming, filled row by row.

How it works

Section titled “How it works”

Index arithmetic you’ll use constantly

Section titled “Index arithmetic you’ll use constantly”
Thing Formula
flat index (row-major) i = r * cols + c
back to 2-D r = i // cols, c = i % cols
main diagonal key r − c (constant along ↘)
anti-diagonal key r + c (constant along ↙), from 0 to rows + cols − 2
rotate 90° clockwise (n×n) (r, c) → (c, n − 1 − r)
transpose (r, c) → (c, r)
mirror left-right (r, c) → (r, cols − 1 − c)
in bounds 0 <= r < rows and 0 <= c < cols

Spiral order with shrinking bounds

Section titled “Spiral order with shrinking bounds”
  1. Set inclusive bounds top = 0, bottom = rows − 1, left = 0, right = cols − 1.
  2. Walk the top edge left→right, then move top down; walk the right edge top→bottom, then move right left.
  3. Only if rows remain, walk the bottom edge right→left; only if columns remain, walk the left edge bottom→top. These guards stop a single leftover row or column being visited twice.
  4. Repeat while top <= bottom and left <= right.
spiral.py
def spiral(m: list[list[int]]) -> list[int]:
    """Values of a rows x cols matrix in clockwise spiral order."""
    if not m or not m[0]:
        return []
    out: list[int] = []
    top, bottom, left, right = 0, len(m) - 1, 0, len(m[0]) - 1  # 1. inclusive bounds
    while top <= bottom and left <= right:
        out += [m[top][c] for c in range(left, right + 1)]  # 2. top edge, then shrink
        top += 1
        out += [m[r][right] for r in range(top, bottom + 1)]  # right edge
        right -= 1
        if top <= bottom:  # 3. guard: a single leftover row must not be walked twice
            out += [m[bottom][c] for c in range(right, left - 1, -1)]
            bottom -= 1
        if left <= right:  # same for a single leftover column
            out += [m[r][left] for r in range(bottom, top - 1, -1)]
            left += 1
    return out




if __name__ == "__main__":
    assert spiral([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) == [1, 2, 3, 6, 9, 8, 7, 4, 5]
    assert spiral([[1, 2, 3, 4], [5, 6, 7, 8]]) == [1, 2, 3, 4, 8, 7, 6, 5]
    assert spiral([[1], [2], [3]]) == [1, 2, 3]
    assert spiral([]) == []
    print("ok")

In-place rotation and neighbours

Section titled “In-place rotation and neighbours”

A 90° clockwise rotation is two easy flips: transpose (swap across the diagonal), then reverse each row. Step through it:

Rotate 90° in place = transpose + reverse rows
step through
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
phasestart
swaps0
being swappeddiagonal (stays put while transposing)final position
Goal: rotate 90° clockwise in place. Cell (r, c) must end up at (c, n−1−r). Doing it as two simple flips avoids juggling four-way cycles.
1 / 17
  1. Transpose: for each i, swap m[i][j] with m[j][i] for j > i only.
  2. Reverse every row.
  3. For grid searches, generate neighbours from a direction list and check bounds before indexing.
rotate_clockwise / neighbors4.py
def rotate_clockwise(m: list[list[int]]) -> None:
    """Rotate a square n x n matrix 90 degrees clockwise, in place."""
    n = len(m)
    for i in range(n):  # 1. transpose: swap across the main diagonal
        for j in range(i + 1, n):  # j > i only, or each pair swaps back
            m[i][j], m[j][i] = m[j][i], m[i][j]
    for row in m:  # 2. reverse each row
        row.reverse()




def neighbors4(r: int, c: int, rows: int, cols: int) -> list[tuple[int, int]]:
    """In-bounds up/down/left/right neighbours: the building block of every grid search."""
    out = []
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):  # 3. direction vectors, not 4 copy-pasted ifs
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:  # 4. bounds check before indexing
            out.append((nr, nc))
    return out




if __name__ == "__main__":
    m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    rotate_clockwise(m)
    assert m == [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
    one = [[1]]
    rotate_clockwise(one)
    assert one == [[1]]
    assert sorted(neighbors4(0, 0, 3, 3)) == [(0, 1), (1, 0)]
    assert len(neighbors4(1, 1, 3, 3)) == 4
    print("ok")

Grids in each language

Section titled “Grids in each language”
Python TypeScript C#
create R×C of zeros [[0] * C for _ in range(R)] Array.from({ length: R }, () => new Array(C).fill(0)) new int[R, C] (rectangular) or new int[R][] + rows (jagged)
the aliasing trap [[0] * C] * R shares one row new Array(R).fill(new Array(C)) shares one row n/a for int[,]
dimensions len(g), len(g[0]) g.length, g[0].length g.GetLength(0), g.GetLength(1) / g.Length, g[0].Length
copy [row[:] for row in g] g.map((row) => row.slice()) (int[,])g.Clone()
visited set key (r, c) tuple `${r},${c}` or r * cols + c (r, c) tuple, or a bool[R, C]
transpose (new) list(map(list, zip(*g))) nested map nested loops

What it costs

Section titled “What it costs”
Time Space
visit every cell O(R · C) O(1) beyond the grid
BFS / DFS over cells O(R · C) (each cell once, ≤ 4 or 8 edges) O(R · C) visited + queue/stack
transpose / rotate in place (n×n) O(n²) O(1)
rotate into a new matrix O(R · C) O(R · C)
2-D prefix sums build / query O(R · C) / O(1) O(R · C)

Traversal order matters in practice. Grids are stored row by row. Row-major loops (for r: for c:) read memory sequentially; column-major loops jump cols slots each step and can be several times slower on large grids, though both are O(R · C).

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Implicit grids. The grid is never stored: “a knight on an infinite board”, “a lock with 4 wheels”. Generate neighbours on the fly and keep only a visited set.
  • Grid as a graph with weights. Moving costs differ per cell: Dijkstra instead of BFS. See shortest path.
  • In-place marking. Overwrite visited cells (e.g. set to 0 or '#') instead of a separate set. Saves memory; mutates input, so say so.
  • Layers / rings. Process the outer ring, then the next one in: layer from 0 to min(R, C) // 2.
  • Sparse grids. Most cells empty and the board huge or unbounded: store only occupied cells in a hash map keyed by (r, c). See hash maps.
  • Diagonal buckets. Group cells by r − c or r + c to check diagonals (N-queens style conflicts) in O(1).

Pitfalls

Section titled “Pitfalls”
  • Swapping r and c. Pick (row, col) = (y, x) once and keep it. grid[x][y] bugs are the most common grid mistake.
  • Bounds check after indexing. In Python, grid[-1] silently wraps to the last row instead of failing. Check bounds first.
  • Non-square grids. Code tested only on 3×3 often breaks on 1×N, N×1 or 2×5. Test them.
  • Aliased rows from [[0] * C] * R or .fill(array).
  • Mutating while scanning. Updating cells in the same pass you read them (Game of Life style) uses half-updated neighbours. Use a copy, or encode old and new state in the same cell.
  • Recursion depth in DFS flood fill: a 1000×1000 all-land grid is a million-deep recursion. Use an explicit stack or BFS.

In the interview

Section titled “In the interview”
  • Ask the dimensions and whether it can be empty or non-square: “Can rows be 0? Is every row the same length?”
  • Ask about neighbours: 4-directional or 8? Does the grid wrap around?
  • Ask whether you may modify the grid in place.
  • Name the graph view out loud: “Each cell is a node with up to four edges, so this is BFS: O(R·C) time and space.”
  • Follow-ups: “the grid is too big for memory” (stream rows; keep only what the next row needs), “cells change over time” (incremental updates, union-find), “now 3-D” (same code, six direction vectors).

Check yourself

Section titled “Check yourself”
Check yourself
pick one
To rotate an n×n matrix 90° clockwise in place, you transpose it and then…
Check yourself
pick one
A 3×4 grid is stored row-major in a flat array. Which (row, col) is at flat index 7?
Check yourself
pick one
In spiral order on a 3×1 grid (one column), what goes wrong without the 'if left <= right' guard on the left edge?

Practice on your own

Section titled “Practice on your own”

Classic textbook exercises, not gym questions:

  • Set matrix zeroes: if a cell is 0, zero its whole row and column, using O(1) extra space.
  • Search a matrix whose rows and columns are both sorted (start from the top-right corner).
  • Game of Life: compute the next generation in place.
  • Diagonal traverse: return all cells in zig-zag diagonal order.

Go deeper

Section titled “Go deeper”
Section titled “Related”
Breadth-first searchFewest moves on a grid.
Depth-first searchFlood fill and connected regions.
2-D dynamic programmingTables filled cell by cell.
Union-findRegions that merge as cells change.