Algorithms
Matrix Algorithms
Difficulty: Intermediate
Rotating an n x n image 90 degrees clockwise sounds like it needs a second matrix to hold the output. The standard trick is two passes over the same matrix: transpose it (swap rows and columns), then reverse each row, and the rotation...
Matrix Algorithms
Rotating an n x n image 90 degrees clockwise sounds like it needs a second matrix to hold the output. The standard trick is two passes over the same matrix: transpose it (swap rows and columns), then reverse each row, and the rotation appears in place with no extra memory. Almost every matrix interview problem hides a similar two-step decomposition under what looks like a hard spatial puzzle.
Matrix Algorithms trains those decompositions. You will implement spiral, diagonal, snake, and anti-diagonal traversals by managing the four boundary indices that change as the walk continues. You will rotate by 90, 180, and 270 degrees in place. You will search sorted matrices three ways: per-row binary search, the staircase search that runs in O(m + n) on row-and-column-sorted matrices, and a single binary search when the whole matrix is sorted. The lesson finishes with in-place transformations like "set matrix zeroes" and Conway's Game of Life that encode state inside the matrix itself.
In Matrix/Grid Fundamentals, you learned how 2D arrays are laid out and indexed. Iteration Patterns on Arrays/Strings taught you single and nested loops in 1D; matrix algorithms layer those patterns across rows and columns with careful boundary management.
From here, Dynamic Programming (Advanced) revisits 2D structures, this time as DP tables.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Implement spiral order traversal of an m x n matrix by managing four boundaries.
Rotate a matrix 90 degrees clockwise using the transpose-then-reverse-rows technique.
Search a row-and-column sorted matrix in O(m + n) time using the staircase approach.
Transform a matrix in-place by marking rows and columns to zero without extra space.
Trace diagonal and zigzag traversal patterns across a matrix.
Analyse the time and space complexity of each matrix algorithm.
Why This Matters
01
Spiral order traversal and matrix rotation are among the most commonly asked medium-difficulty interview problems — they test boundary management and spatial reasoning.
02
Searching in a sorted matrix with staircase search achieves O(m + n) — far better than the naive O(m * n) scan, a classic interview optimisation.
03
In-place matrix transformations like 'set matrix zeroes' test the ability to avoid extra space by encoding state within the matrix itself.
04
Matrix problems appear in image processing, game boards, spreadsheet engines, and scientific computing.
Key Terms
6 terms you'll encounter in this lesson
Spiral order
Traversing a matrix layer by layer from outside to inside: right along the top row, down the right column, left along the bottom row, up the left column, then repeat for inner layers.
Transpose
Swapping rows and columns of a matrix: element at (i, j) moves to (j, i). For a square matrix this can be done in-place.
Staircase search
Starting from the top-right (or bottom-left) corner of a row-and-column sorted matrix. Move left if the value is too large, down if too small. Eliminates one row or column per step.
Diagonal traversal
Visiting matrix elements along diagonals. Elements on the same diagonal satisfy i + j = constant (or i - j = constant for anti-diagonals).
In-place transformation
Modifying a matrix without allocating a separate copy. Often achieved by encoding information in the matrix itself (e.g., using the first row/column as markers).
Row-and-column sorted matrix
A matrix where each row is sorted left-to-right and each column is sorted top-to-bottom. Enables O(m+n) search via staircase.
Heads Up
Common misconceptions to watch out for
"Spiral traversal requires recursion"
Spiral traversal is best done iteratively with four boundary variables (top, bottom, left, right). Recursion adds unnecessary complexity and stack overhead for this pattern.
"Rotating a matrix 90 degrees requires extra space"
For square matrices, rotate in-place using transpose + reverse rows. Transpose swaps (i,j) with (j,i), then reversing each row completes the 90-degree clockwise rotation. No extra matrix needed.
"Binary search works directly on a row-and-column sorted matrix"
A row-and-column sorted matrix is NOT fully sorted in one sequence. Binary search on the flattened array only works if the matrix is fully sorted (last element of row i <= first element of row i+1). For row-and-column sorted matrices, use staircase search.