A matrix is just a 2D array — an array of arrays. We access elements with two indices: matrix[row][col]. Think of it like a spreadsheet — rows go across, columns go down.
Matrices show up a lot in interviews: image rotation, game boards, grids, graphs represented as adjacency matrices. The key is getting comfortable with the indexing and the common traversal patterns.
Row-Major Indexing
In most languages, matrices are stored in row-major order — all elements of row 0 come first in memory, then row 1, then row 2, etc.
Quick cheat sheet for matrix dimensions:
rows = matrix.lengthcols = matrix[0].length- To visit every element: nested loop over
rowsandcols
Spiral Order Traversal
Spiral traversal visits elements in a clockwise spiral: right across the top, down the right side, left across the bottom, up the left side, then repeat on the inner ring.
The approach: maintain four boundaries (top, bottom, left, right) and shrink them inward after processing each side.
function spiralOrder(matrix) {
const result = [];
let top = 0, bottom = matrix.length - 1;
let left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
// go right across top row
for (let c = left; c <= right; c++) result.push(matrix[top][c]);
top++;
// go down right column
for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);
right--;
// go left across bottom row (if rows remain)
if (top <= bottom) {
for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);
bottom--;
}
// go up left column (if cols remain)
if (left <= right) {
for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);
left++;
}
}
return result;
}
console.log(spiralOrder([[1,2,3],[4,5,6],[7,8,9]]));
// [1, 2, 3, 6, 9, 8, 7, 4, 5]def spiral_order(matrix):
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
# go right across top row
for c in range(left, right + 1):
result.append(matrix[top][c])
top += 1
# go down right column
for r in range(top, bottom + 1):
result.append(matrix[r][right])
right -= 1
# go left across bottom row (if rows remain)
if top <= bottom:
for c in range(right, left - 1, -1):
result.append(matrix[bottom][c])
bottom -= 1
# go up left column (if cols remain)
if left <= right:
for r in range(bottom, top - 1, -1):
result.append(matrix[r][left])
left += 1
return result
print(spiral_order([[1,2,3],[4,5,6],[7,8,9]]))
# [1, 2, 3, 6, 9, 8, 7, 4, 5]public static List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (int c = left; c <= right; c++) result.add(matrix[top][c]);
top++;
for (int r = top; r <= bottom; r++) result.add(matrix[r][right]);
right--;
if (top <= bottom) {
for (int c = right; c >= left; c--) result.add(matrix[bottom][c]);
bottom--;
}
if (left <= right) {
for (int r = bottom; r >= top; r--) result.add(matrix[r][left]);
left++;
}
}
return result;
}
// [[1,2,3],[4,5,6],[7,8,9]] → [1, 2, 3, 6, 9, 8, 7, 4, 5]Time: O(m × n), Space: O(1) — we visit every element exactly once (output array doesn’t count as extra space).
Rotate Matrix 90 Degrees
Rotating a matrix 90 degrees clockwise is a classic interview question (LeetCode 48). The trick is a two-step process:
- Transpose — swap
matrix[i][j]withmatrix[j][i](rows become columns) - Reverse each row — flip every row left-to-right
That’s it. Transpose + reverse = 90-degree clockwise rotation.
function rotate(matrix) {
const n = matrix.length;
// Step 1: transpose (swap across diagonal)
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]];
}
}
// Step 2: reverse each row
for (let i = 0; i < n; i++) {
matrix[i].reverse();
}
return matrix;
}
console.log(rotate([[1,2,3],[4,5,6],[7,8,9]]));
// [[7,4,1],[8,5,2],[9,6,3]]def rotate(matrix):
n = len(matrix)
# Step 1: transpose (swap across diagonal)
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Step 2: reverse each row
for row in matrix:
row.reverse()
return matrix
print(rotate([[1,2,3],[4,5,6],[7,8,9]]))
# [[7,4,1],[8,5,2],[9,6,3]]public static void rotate(int[][] matrix) {
int n = matrix.length;
// Step 1: transpose (swap across diagonal)
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// Step 2: reverse each row
for (int[] row : matrix) {
int l = 0, r = n - 1;
while (l < r) {
int temp = row[l];
row[l++] = row[r];
row[r--] = temp;
}
}
}
// [[1,2,3],[4,5,6],[7,8,9]] → [[7,4,1],[8,5,2],[9,6,3]]Time: O(n²), Space: O(1) — done in-place.
Rotation cheat sheet:
- 90° clockwise = transpose + reverse rows
- 90° counter-clockwise = transpose + reverse columns
- 180° = reverse rows + reverse columns
Search in a Sorted Matrix
When the matrix is sorted (each row is sorted left-to-right, and the first element of each row is greater than the last element of the previous row), we can search in O(log(m × n)) using binary search. We treat the 2D matrix as a flat sorted array.
But there’s a simpler variant: rows are sorted left-to-right AND columns are sorted top-to-bottom (but no guarantee between rows). For this, we use the staircase search — start from the top-right corner.
function searchMatrix(matrix, target) {
// Start from top-right corner
let row = 0;
let col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] === target) return true;
if (matrix[row][col] > target) {
col--; // too big, go left
} else {
row++; // too small, go down
}
}
return false;
}
const matrix = [
[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16],
[10, 13, 14, 17]
];
console.log(searchMatrix(matrix, 5)); // true
console.log(searchMatrix(matrix, 20)); // falsedef search_matrix(matrix, target):
# Start from top-right corner
row, col = 0, len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
if matrix[row][col] == target:
return True
if matrix[row][col] > target:
col -= 1 # too big, go left
else:
row += 1 # too small, go down
return False
matrix = [
[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16],
[10, 13, 14, 17]
]
print(search_matrix(matrix, 5)) # True
print(search_matrix(matrix, 20)) # Falsepublic static boolean searchMatrix(int[][] matrix, int target) {
// Start from top-right corner
int row = 0, col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] == target) return true;
if (matrix[row][col] > target) col--; // go left
else row++; // go down
}
return false;
}
// Search for 5 → true, search for 20 → falseTime: O(m + n), Space: O(1) — we eliminate one row or column with each step.
Why does starting from the top-right work? Because going left decreases the value and going down increases it. This gives us a clear decision at every step — no backtracking needed.
Common Matrix Traversal Patterns
Here’s a quick reference for the traversal patterns that come up most often:
| Pattern | When to Use | Key Idea |
|---|---|---|
| Row-by-row | Basic processing | Two nested loops |
| Column-by-column | Transpose-like operations | Outer loop = col, inner = row |
| Spiral | Print/flatten in spiral order | Four boundaries, shrink inward |
| Diagonal | Zigzag or diagonal grouping | i + j = constant for each diagonal |
| BFS/DFS on grid | Connected components, shortest path | Treat each cell as a graph node |
In simple language, matrix problems are really just array problems in 2D. The hard part isn’t the algorithm — it’s keeping track of the boundaries and not going out of bounds. The spiral traversal and rotation by transpose+reverse are the two patterns that show up most in interviews. Get those down and the rest follows.