CODING PATTERNS · LESSON 17 OF 28 · 62 MIN VIDEO · 20 PROBLEMS

Matrices

Module Progress (0 / 20 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (62 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Matrices — How the Pattern Works

Matrix traversal and manipulation patterns solve 2D grid problems by pairing deliberate cell-visiting orders—row-major, concentric boundary rings, zigzag anti-diagonals, monotonic staircases, or BFS/Dijkstra frontiers—with coordinate invariants and in-place state encoding. Maintaining structural invariants such as shrinking ring bounds [top, bottom, left, right], monotonic column pointers on doubly sorted grids, or composite cell codes that preserve previous states alongside next states eliminates auxiliary O(m * n) grid copies and reduces brute-force O(m * n) or exponential searches to O(m + n), O(m log(m * n)), or single-pass O(m * n) algorithms.

WHEN TO USE THIS PATTERN
  • The input is an m x n 2D grid requiring non-trivial traversal geometry such as concentric clockwise spirals, alternating diagonals, 90-degree in-place rotations, matrix transposition, or 1D-to-2D index reshaping.
  • Constraints demand O(1) auxiliary space while modifying rows, columns, or simultaneous multi-cell generations that would otherwise cascade or overwrite unread neighbor states.
  • Rows and columns exhibit monotonic ordering (explicitly sorted grids or implicit products r * c), enabling O(m + n) staircase elimination from a saddle corner or binary search over the value range.
  • Cells interact through 4-directional or 8-directional adjacency—counting exposed perimeters, bounding connected components, racing multi-source hazard BFS fronts, or minimizing path bottleneck elevations with a min-heap.
  • Grid operations apply uniformly across an axis or decompose additively by coordinate, allowing row canonicalization via hash maps or decoupling 2D Manhattan distances into independent 1D medians.
COMMON INTERVIEW PITFALLS
  • Re-reading degenerate inner strips in Spiral Matrix: when m != n and a single row (top == bottom) or single column (left == right) remains after advancing top and right, omitting the if top <= bottom and if left <= right guards traverses that final strip a second time in reverse.
  • Double-swapping across the main diagonal during in-place transpose: starting the column loop at c = 0 instead of c = r + 1 swaps (r, c) with (c, r) twice and leaves the matrix unchanged.
  • Overwriting margin markers or unread states prematurely: clearing row 0 or column 0 before finishing the inner subgrid in Set Matrix Zeroes destroys column/row markers, and writing final 0/1 values mid-pass in Game of Life corrupts neighbor counts for subsequent cells.
  • Checking non-corner bounds first in Diagonal Traverse: at the top-right corner (0, n - 1) while moving up-right, testing r < 0 (slide right to c + 1) before testing c == n - 1 (slide down to r + 1) pushes the column index out of bounds.
Four-Boundary Shrinking Ring Traversal (Spiral)Read or populate an m x n matrix in concentric clockwise layers using O(1) auxiliary space.
top, bottom, left, right = 0, len(mat) - 1, 0, len(mat[0]) - 1
while top <= bottom and left <= right:
    for c in range(left, right + 1): visit(mat[top][c])
    top += 1
    for r in range(top, bottom + 1): visit(mat[r][right])
    right -= 1
    if top <= bottom:
        for c in range(right, left - 1, -1): visit(mat[bottom][c])
        bottom -= 1
    if left <= right:
        for r in range(bottom, top - 1, -1): visit(mat[r][left])
        left += 1
In-Place Transpose + Reflection (90° Clockwise Rotation)Rotate an n x n square matrix 90 degrees clockwise in-place without allocating an O(n^2) copy.
def rotate_clockwise(mat):
    n = len(mat)
    for r in range(n):
        for c in range(r + 1, n):
            mat[r][c], mat[c][r] = mat[c][r], mat[r][c]
    for row in mat:
        row.reverse()
Staircase Scan on Doubly Sorted MatrixCount or search in O(m + n) time when every row and every column is monotonically sorted.
def staircase_count(grid):
    n = len(grid[0])
    c, total = n, 0
    for row in grid:
        while c > 0 and row[c - 1] < 0:
            c -= 1
        total += n - c
    return total
In-Place Multi-State EncodingUpdate all grid cells simultaneously in O(1) extra space when transitions depend on original neighbor states.
def simultaneous_update(board):
    m, n = len(board), len(board[0])
    for r in range(m):
        for c in range(n):
            prev = count_neighbors_in_states(board, r, c, (1, 2))
            if board[r][c] == 1 and dies(prev):
                board[r][c] = 2  # was 1, becomes 0
            elif board[r][c] == 0 and born(prev):
                board[r][c] = 3  # was 0, becomes 1
    for r in range(m):
        for c in range(n):
            board[r][c] %= 2

01. Set Matrix Zeroes

Optimal Target: O(m × n) time · O(1) extra space

Given an m x n integer grid matrix, if an element matrix[r][c] is 0, set its entire row r and its entire column c to 0. Modify matrix in-place without returning a new grid, using O(1) extra space.

EXAMPLE 1
Input: matrix = [[1, 2, 3, 4], [5, 6, 0, 8], [9, 1, 2, 3], [4, 5, 6, 7]]
Output: [[1, 2, 0, 4], [0, 0, 0, 0], [9, 1, 0, 3], [4, 5, 0, 7]]
Explanation: Only matrix[1][2] is initially 0, so every entry in row 1 and column 2 becomes 0 while all other cells keep their original values.
EXAMPLE 2
Input: matrix = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
Output: [[0, 0, 0], [0, 4, 5], [0, 7, 8]]
Explanation: Because matrix[0][0] == 0 lies in both the first row and first column, row 0 and column 0 are zeroed out completely.
VISUAL INPUT
1234
5608
9123
4567
AUTOMATED TEST SUITE
Test Case 1
Input: [[1, 2, 3, 4], [5, 6, 0, 8], [9, 1, 2, 3], [4, 5, 6, 7]]
Expected: [[1, 2, 0, 4], [0, 0, 0, 0], [9, 1, 0, 3], [4, 5, 0, 7]]
Test Case 2
Input: [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
Expected: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
Test Case 3
Input: [[1, 0, 3]]
Expected: [[0, 0, 0]]
Pattern Trigger Hint ("How to Spot It")

marks per row or column, no extra memory

Python 3.14 Runtime Ready

Click ▶ Run Tests (or press ⌘+Enter) to execute set_zeroes against all 3 test cases in WebAssembly Python.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

Take the top right corner of our four by four grid. Stepping only up, down, left or right, how many neighbors does it have?