Matrix / Shape

"Matrix traversal, rotation, spiral, set zeroes, word search, island perimeter, game of life."

Deep Dive Tutorial

Matrix problems look intimidating because 2D indexing is fiddly. The secret is that almost every matrix problem reduces to one of 5-6 core techniques. Once you see which technique applies, the implementation is mostly mechanical.

Core Techniques

Problem Type	Technique
Traverse all cells in spiral order	Direction array + boundary shrink
Rotate matrix 90° clockwise	Transpose then reverse each row
Rotate 90° counter-clockwise	Reverse each row then transpose
Diagonal traversal	Sum of indices is constant on each diagonal
Count valid submatrix sums	2D prefix sum in O(1) query
Search in row+col sorted matrix	Start top-right: go left if too big, down if too small
Count cells equal to target sum	2D prefix sum + column compression

Rotate matrix 90° clockwise in-place

// Step 1: Transpose (swap arr[i][j] with arr[j][i])
// Step 2: Reverse each row
var rotate = function(matrix) {
    const n = matrix.length;
    // Transpose
    for (let i = 0; i < n; i++)
        for (let j = i + 1; j < n; j++)
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    // Reverse each row
    for (const row of matrix) row.reverse();
};

2D Prefix Sum — build in O(n²), query any rectangle in O(1)

// prefix[i][j] = sum of all cells in rectangle (0,0) to (i-1, j-1)
function build2DPrefix(matrix) {
    const n = matrix.length, m = matrix[0].length;
    const prefix = Array.from({length: n+1}, () => new Array(m+1).fill(0));
    for (let i = 1; i <= n; i++)
        for (let j = 1; j <= m; j++)
            prefix[i][j] = matrix[i-1][j-1]
                + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
    return prefix;
}
// Query rectangle (r1,c1) to (r2,c2) (0-indexed):
const query = (p, r1, c1, r2, c2) =>
    p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1];

Search in 2D matrix sorted by rows and columns

// Start at top-right corner.
// If target < current: move left (current column too big)
// If target > current: move down (current row too small)
// Each step eliminates an entire row or column → O(n+m)
var searchMatrix = function(matrix, target) {
    let r = 0, c = matrix[0].length - 1;
    while (r < matrix.length && c >= 0) {
        if (matrix[r][c] === target) return true;
        else if (matrix[r][c] > target) c--;
        else r++;
    }
    return false;
};

Worked Problems

Spiral Matrix

Medium

Solve ↗

Number of Submatrices That Sum to Target

Hard

Solve ↗

Maximal Square

Medium

Solve ↗

Matrix / Shape

Deep Dive Tutorial

Core Techniques

Worked Problems

More Worked Problems