Skip to content
Companies
    
DSA Patterns

Learn

Matrix Manipulation

The four matrix techniques interviews reuse: transpose-then-reverse rotation, boundary-shrinking spiral traversal, first-row/column marking, and treating a sorted grid as one array.

3 min readUpdated 2 Sept 2026

#Matrix#Arrays#In-place#Binary Search

Matrix questions are index bookkeeping, and they get asked because index bookkeeping under pressure is where people fall apart. There is no deep algorithm here — there are four specific tricks, and knowing them turns a fiddly twenty minutes into five.

Rotate: transpose, then reverse

Rotating 90° clockwise in place looks like it needs a four-way cyclic swap. It does not. Transpose the matrix (mirror across the main diagonal), then reverse each row.

def rotate(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):                       # upper triangle only
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()
1 2 3      transpose      1 4 7      reverse rows      7 4 1
4 5 6   ──────────────▶   2 5 8   ──────────────────▶  8 5 2
7 8 9                     3 6 9                        9 6 3

j starts at i + 1, not 0 — swapping the whole grid transposes it twice and gets you back where you started. For counter-clockwise, reverse the columns instead (or reverse the row order first, then transpose).

Spiral: four shrinking boundaries

Track top, bottom, left, right. Walk one edge, retract that boundary, repeat.

def spiral_order(matrix):
    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])
        top += 1

        for r in range(top, bottom + 1):
            out.append(matrix[r][right])
        right -= 1

        if top <= bottom:                       # guard: the row may be gone
            for c in range(right, left - 1, -1):
                out.append(matrix[bottom][c])
            bottom -= 1

        if left <= right:                       # guard: the column may be gone
            for r in range(bottom, top - 1, -1):
                out.append(matrix[r][left])
            left += 1

    return out

The two mid-loop guards are the whole difficulty. A single leftover row or column gets walked twice without them, and the bug only shows on non-square inputs — which is exactly what the test cases contain.

Set Matrix Zeroes: use row 0 and column 0 as the marks

Zeroing rows and columns in place is a classic O(1)-space question. Writing a zero as you go corrupts the input for later reads, and a separate set of flags costs O(m + n). The trick is to store those flags in the matrix itself: the first cell of each row and column marks whether that row or column must be cleared.

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_col_zero = any(matrix[r][0] == 0 for r in range(rows))

    for r in range(rows):                       # mark
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = matrix[0][c] = 0

    for r in range(rows - 1, -1, -1):           # apply, bottom-up
        for c in range(cols - 1, 0, -1):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0
        if first_col_zero:
            matrix[r][0] = 0

Column 0 needs its own flag because matrix[0][0] is shared between the row-0 marker and the column-0 marker, and applying bottom-up keeps the markers readable until they are used.

Search: treat a sorted grid as one array

Search a 2D Matrix — rows sorted, each row starting after the previous ends — is a plain

binary search on m * n with index arithmetic:

# Search a 2D Matrix — rows chain, so it is one binary search over m*n
mid_value = matrix[mid // cols][mid % cols]

Search a 2D Matrix II is different: rows and columns are each sorted, but rows do not

chain. Start at the top-right corner — the one cell where moving left always decreases and moving down always increases — and walk:

def search_matrix_ii(matrix, target):
    r, c = 0, len(matrix[0]) - 1
    while r < len(matrix) and c >= 0:
        if matrix[r][c] == target:
            return True
        if matrix[r][c] > target:
            c -= 1          # whole column below is too big
        else:
            r += 1          # whole row to the left is too small
    return False

O(m + n): each step eliminates an entire row or column.

Complexity

Rotate, spiral and set-zeroes are O(m × n) time — every cell is touched a constant number of times — with O(1) extra space. 2D binary search is O(log(m × n)); the staircase search is O(m + n).

Mistakes that cost the round

  • Transposing the whole grid instead of the upper triangle.
  • Missing the spiral's mid-loop guards, which double-visits a single leftover line.
  • Writing zeroes during the marking pass in Set Matrix Zeroes, which cascades.
  • Confusing the two search problems. Chained rows → binary search. Independently

sorted rows and columns → staircase from a corner.

  • Assuming a square matrix. Use len(matrix) and len(matrix[0]) separately, always.

What to drill

  1. Set Matrix Zeroes — in-place marking.
  2. Spiral Matrix — boundaries and guards.
  3. Rotate Image — transpose plus reverse.
  4. Search a 2D Matrix — flatten and binary search.

All on the 22 DSA Patterns sheet.

Frequently asked

How do you rotate a matrix 90 degrees in place?

Transpose it — swap matrix[i][j] with matrix[j][i] for the upper triangle only — then reverse each row. That gives a clockwise rotation with O(1) extra space. For counter-clockwise, transpose and reverse the columns instead.

How do you set matrix zeroes in O(1) space?

Use the first row and first column as the marker storage. Scan the rest of the grid and, for each zero, set the marker at the start of its row and column. Then apply the markers bottom-up and right-to-left so they stay readable. Column 0 needs a separate boolean because matrix[0][0] serves as both markers.

Why start at the top-right corner when searching a sorted matrix?

Because it is the only corner where the two directions disagree: moving left strictly decreases the value and moving down strictly increases it. Each comparison therefore eliminates an entire row or column, giving O(m + n). Starting at the top-left leaves both directions increasing, which tells you nothing.

Related

Cyclic Sort (Index-Based)

When the values are 1..n, the array is its own hash map — swap each value home and read off what is missing.

Modified Binary Search

One boundary template, then the two hard variants: rotated arrays, and searching the answer space instead of the input.

Reversal of Linked List (In-place)

Three pointers, one pass, no extra memory — and the dummy node that makes the sublist variants tractable.