Pattern Guide
Matrix & Shape Problems
"Spiral traversal, rotation, 2D prefix sums — grids have patterns."
Matrix problems form their own family. Spiral traversal, 90° rotation, diagonal traversal, 2D prefix sums, and binary search in sorted matrices all have elegant O(n) or O(n²) solutions once you see the pattern.
16 min readshape problems →
Problems you can solve with this pattern
5 problems · click any to start solving
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();
};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;
};2D prefix sum formula (memorize this):
prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
Query rectangle (r1,c1)→(r2,c2):
sum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]
The +1 offset keeps the prefix 1-indexed so you can safely access prefix[i-1] without bounds checks.
prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
Query rectangle (r1,c1)→(r2,c2):
sum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]
The +1 offset keeps the prefix 1-indexed so you can safely access prefix[i-1] without bounds checks.