Matrices

The matrix (2D grid) coding pattern for interviews. Walking a grid, layers and spirals, rotating and marking cells in place, with a step-through, templates in Java, Python, C#, Go and TypeScript, and 10 LeetCode problems.

Foundation13 min read

Read first: Two pointers

A matrix is a grid of values: m rows, n columns, and a cell at grid[row][column]. Images, game boards, maps and spreadsheets are all matrices. Matrix problems rarely need a clever algorithm. They need careful index work: which way you walk, where you stop, and how you avoid reading a cell you already changed.

This page covers the three moves that most matrix questions use. Walk the grid with clear bounds. Peel it in layers, the rings from the outside in. And mark cells in place, so you don’t need a second grid. When a grid question is really “which cells can reach which”, it’s a graph. Then the answer is on the graph search page.

How to spot it

The input is a 2D array: a board, an image, a map or a table.
“Rotate”, “transpose”, “spiral”, “diagonal”. These are walks in a fixed order, and the work is in the indexes.
“In place” or “O(1) extra memory” on a grid. You’ll need to keep notes inside the grid.
Every cell’s new value depends on its neighbors’ old values, as in Game of Life. You need to keep the old values readable while you write new ones.
A sorted grid. Rows and columns sorted means you can rule out a whole row or column with one comparison.

Watch it run

Read a 4 × 4 grid in spiral order. The four walls fence in the cells not yet taken. Watch how each side is taken and then its wall moves in by one. When the walls cross, the grid is done.

row \ column	0	1	2	3
0	1	2	3	4
1	5	6	7	8
2	9	10	11	12
3	13	14	15	16

walls

top 0bottom 3left 0right 3

output

empty

top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
take top row →; top += 1
take right column ↓; right -= 1
if top <= bottom:
take bottom row ←; bottom -= 1
if left <= right:
take left column ↑; left += 1

Four walls fence in the cells not yet taken. The highlighted block is everything still inside them.

1 / 9

The walls make the loop safe without a visited grid. A cell outside the walls is always taken, and a cell inside is never taken. There’s one trap. After the top row and the right column are taken, only one row or one column may be left. The checks if top <= bottom and if left <= right stop the loop from taking that last line twice, once in each direction.

The template

Spiral order with walls, rotation in place, and setting zeroes with the first row and column as markers:

Matrices.javaexample.pyMatrices.csmain.goexample.ts

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Matrices {
    static List<Integer> spiralOrder(int[][] matrix) {
        // Spiral order with four walls around the part not yet taken. Take one side, then move that
        // wall inward. Every cell is taken once: O(m·n) time for m rows and n columns, O(1) extra
        // memory beyond the output.
        List<Integer> result = new ArrayList<>();
        int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int column = left; column <= right; column++) {
                result.add(matrix[top][column]);
            }
            top++;
            for (int row = top; row <= bottom; row++) {
                result.add(matrix[row][right]);
            }
            right--;
            // The checks stop a single leftover row or column from being taken twice.
            if (top <= bottom) {
                for (int column = right; column >= left; column--) {
                    result.add(matrix[bottom][column]);
                }
                bottom--;
            }
            if (left <= right) {
                for (int row = bottom; row >= top; row--) {
                    result.add(matrix[row][left]);
                }
                left++;
            }
        }
        return result;
    }

    static void rotate(int[][] matrix) {
        // Rotate a square grid 90° clockwise in place. A transpose (swap across the main
        // diagonal) followed by reversing each row moves every cell to its rotated spot.
        // O(n²) time for an n × n grid, O(1) memory.
        int size = matrix.length;
        for (int row = 0; row < size; row++) {
            // column > row, so each pair swaps once, not twice.
            for (int column = row + 1; column < size; column++) {
                int saved = matrix[row][column];
                matrix[row][column] = matrix[column][row];
                matrix[column][row] = saved;
            }
        }
        for (int[] row : matrix) {
            for (int i = 0, j = size - 1; i < j; i++, j--) {
                int saved = row[i];
                row[i] = row[j];
                row[j] = saved;
            }
        }
    }

    static void setZeroes(int[][] matrix) {
        // Set a cell's whole row and column to 0 if it holds 0. The first row and first column
        // store the marks, so no extra grid is needed. Their own zeros are remembered in two flags
        // first, because the marks would hide them. O(m·n) time for m rows and n columns, O(1)
        // memory.
        int rowCount = matrix.length, columnCount = matrix[0].length;
        boolean firstRow = false, firstColumn = false;
        for (int column = 0; column < columnCount; column++) firstRow |= matrix[0][column] == 0;
        for (int row = 0; row < rowCount; row++) firstColumn |= matrix[row][0] == 0;
        for (int row = 1; row < rowCount; row++) {
            for (int column = 1; column < columnCount; column++) {
                // Mark row and column.
                if (matrix[row][column] == 0) matrix[row][0] = matrix[0][column] = 0;
            }
        }
        for (int row = 1; row < rowCount; row++) {
            for (int column = 1; column < columnCount; column++) {
                if (matrix[row][0] == 0 || matrix[0][column] == 0) matrix[row][column] = 0;
            }
        }
        // Clear the marker row and column last, so the marks are read before they change.
        if (firstRow) Arrays.fill(matrix[0], 0);
        if (firstColumn) for (int row = 0; row < rowCount; row++) matrix[row][0] = 0;
    }

    public static void main(String[] args) {
        check(spiralOrder(new int[][] {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}})
                .equals(List.of(1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7)));
        check(spiralOrder(new int[][] {{1, 2}, {3, 4}}).equals(List.of(1, 2, 4, 3)));
        check(spiralOrder(new int[][] {{5}, {6}, {7}}).equals(List.of(5, 6, 7)));
        check(spiralOrder(new int[][] {{9}}).equals(List.of(9)));
        int[][] grid = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        rotate(grid);
        check(Arrays.deepEquals(grid, new int[][] {{7, 4, 1}, {8, 5, 2}, {9, 6, 3}}));
        grid = new int[][] {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        setZeroes(grid);
        check(Arrays.deepEquals(grid, new int[][] {{1, 0, 1}, {0, 0, 0}, {1, 0, 1}}));
        grid = new int[][] {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        setZeroes(grid);
        check(Arrays.deepEquals(grid, new int[][] {{0, 0, 0, 0}, {0, 4, 5, 0}, {0, 3, 1, 0}}));
        System.out.println("ok: spiralOrder, rotate and setZeroes");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

Look at the order of steps in set_zeroes. The first row and column are used as notes, so their own zeros are saved in two flags before anything else. They are cleared last, after all the notes are read. Change that order and a note gets erased before it’s used.

Variations

Walking neighbors

Many grid problems look at the four cells next to each cell: up, down, left and right. Keep a list of four direction pairs and loop over it. For each pair, compute the neighbor’s row and column, and skip it if it’s out of bounds. Add the four diagonal pairs when the problem says “eight neighbors”. This one loop is the core of flood fill, islands and shortest paths on a grid.

Rotate by layers

The transpose-and-reverse trick is the easiest to get right. You can also rotate each ring directly. For each layer, take four cells at a time, one on each side, and move them around in a cycle: top to right, right to bottom, bottom to left, left to top. Save one cell in a temporary variable first. Both ways are O(n²) time for an n × n grid and O(1) memory. Counterclockwise is a transpose and then reversing each column.

Old and new values in one cell

Game of Life updates every cell from its neighbors at the same moment. If you write new values directly, later cells read a mix of old and new. Encode both in the cell instead. For example, use 2 for “was alive, now dead” and 3 for “was dead, now alive”. Every neighbor can still tell the old value. A second pass turns 2 into 0 and 3 into 1.

A sorted grid as one array

When every row is sorted and each row starts after the previous one ends, the grid is one sorted array. Use binary search from 0 to row_count * column_count - 1, and turn an index back into a cell with row = index / column_count and column = index % column_count. When rows and columns are each sorted, but not joined, start at the top right corner. A bigger target means moving down, a smaller one means moving left. Each step rules out one row or one column, so it’s O(m + n).

Complexity

	Time	Extra memory
Any full walk: spiral, transpose	O(m·n)	O(1) beyond output
Rotate in place	O(n²)	O(1)
Set zeroes with marker row and col	O(m·n)	O(1)
Set zeroes with two sets	O(m·n)	O(m + n)
Search a row and column sorted grid	O(m + n)	O(1)

Say this out loud

I’ll keep four walls around the part not yet visited. I take the top row and move the top wall down, then the right column, then the bottom row, then the left column. I check the walls before the last two sides, so a single leftover row isn’t taken twice. It’s O(m·n) time.

Interview questions

Interviewer asksSet Matrix Zeroes with O(m + n) memory is easy. How do you get to O(1)?

Use the grid’s own first row and first column as the two sets. A zero at (row, column) marks grid[row][0] and grid[0][column]. The first row and column hold real data too, so first save two flags: does the first row have a zero, does the first column have one. Fill the inner cells from the marks, then clear the first row and column last.

Interviewer asksWhy does transposing and then reversing each row rotate the grid clockwise?

In an n × n grid (size in code), after a 90° clockwise turn, the value at (row, column) lands at (column, size - 1 - row). The transpose moves it to (column, row). Reversing the row moves column row to column size - 1 - row. Together that’s exactly (column, size - 1 - row). It only works in place on a square grid. A grid that isn’t square needs a new grid, because its shape changes.

Interviewer asksThe grid is too big to fit in memory. What can still work?

Anything that reads row by row. Spiral order and rotation need random access, so they would need the grid split into tiles. A search in a row and column sorted grid reads only a path of m + n cells. Set Matrix Zeroes can be done in two passes over the rows, keeping only the set of columns to clear, O(n) memory.

Practice

10 problems on LeetCode: 2 easy, 8 medium

Ticks are saved in this browser only. Clear your site data and they're gone.

Three of these are solved step by step on this site, as part of the Blind 75: Spiral Matrix, Rotate Image and Set Matrix Zeroes. Grids also show up in Number of Islands, Pacific Atlantic Water Flow and Word Search, where the neighbor loop from this page drives a search.

Recap

Use it when the input is a 2D grid and the work is a walk in a fixed order, a rotation, or a change in place.
Walls for layers: take a side, move the wall in, and check before the last two sides.
Neighbors come from a list of directions plus a bounds check.
In place: keep notes in the first row and column, or encode old and new in one cell.
Cost: O(m·n) to touch every cell, O(1) extra memory for all of the moves on this page.
Watch for: rows and columns swapped, and grids that are a single row or column.