Traverse, search, and transform 2D grids using DFS, BFS, and in-place tricks.
A matrix is a 2D array of rows and columns. Matrix problems test your ability to navigate grids — counting islands, finding shortest paths, rotating images, and setting zeros. Key patterns are BFS/DFS for connected-component problems, in-place rotation/transformation, and treating the matrix as a graph.
Traversal O(m × n)
O(m × n) for visited array or BFS queue
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this when you need to move from one cell to its neighbors repeatedly
Instead of writing four separate movement cases everywhere, store the row and column offsets once and loop through them. This keeps grid traversal logic short and less error-prone.
Problem Number of Islands. For every land cell, explore its four neighboring cells using a shared directions array.
// Direction vectors for 4-directional grid traversal
function getNeighbors(row, col, rows, cols) {
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
return dirs
.map(([dr, dc]) => [row + dr, col + dc])
.filter(([r, c]) => r >= 0 && r < rows && c >= 0 && c < cols);
}Use this whenever you access a neighboring cell
Grid bugs often come from invalid indices, so every move should be validated before touching the matrix. A small helper or consistent condition keeps traversal safe.
Problem Word Search. Before exploring the next cell, verify it stays inside the board and has not gone out of bounds.
function inBounds(row, col, rows, cols) {
return row >= 0 && row < rows && col >= 0 && col < cols;
}
// Usage: guard every grid access
function safeGet(grid, row, col) {
const rows = grid.length, cols = grid[0].length;
return inBounds(row, col, rows, cols) ? grid[row][col] : null;
}Use this when you want the shortest number of steps in an unweighted grid or when the process spreads level by level
BFS explores all cells at distance d before distance d + 1, which makes it perfect for shortest path and infection-style problems.
Problem Rotting Oranges. Start with all rotten oranges in the queue and spread rot outward one level at a time.
// BFS on grid — Rotting Oranges
function orangesRotting(grid) {
const rows = grid.length, cols = grid[0].length;
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
const queue = [];
let fresh = 0;
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 2) queue.push([r, c]);
else if (grid[r][c] === 1) fresh++;
}
let minutes = 0;
while (queue.length && fresh > 0) {
let size = queue.length;
while (size--) {
const [row, col] = queue.shift();
for (const [dr, dc] of dirs) {
const nr = row + dr, nc = col + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
grid[nr][nc] = 2; fresh--; queue.push([nr, nc]);
}
}
}
minutes++;
}
return fresh === 0 ? minutes : -1;
}Use this when you want to fully explore one connected region before moving to the next
DFS is often the simplest way to count islands, mark components, or search recursively through a board. The recursive function usually means: if the cell is invalid, stop; otherwise mark it and recurse to neighbors.
Problem Number of Islands. Whenever you find unvisited land, run DFS to mark the whole island before continuing.
// DFS on grid — Number of Islands
function numIslands(grid) {
const rows = grid.length, cols = grid[0].length;
let count = 0;
function dfs(r, c) {
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;
grid[r][c] = '0';
dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
}
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (grid[r][c] === '1') { count++; dfs(r, c); }
return count;
}Use this when modifying the input is allowed and you want to avoid an extra visited matrix
Marking cells directly often reduces space complexity and simplifies the code. The key is to choose a marker value that cannot be confused with an unvisited valid cell.
Problem Number of Islands. Change visited land from '1' to '0' so future traversals naturally skip it.
// In-place marking — mark visited cells directly
// Set Zeroes: mark rows/cols then apply
function setZeroes(matrix) {
const rows = matrix.length, cols = matrix[0].length;
const zeroRows = new Set(), zeroCols = new Set();
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (matrix[r][c] === 0) { zeroRows.add(r); zeroCols.add(c); }
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (zeroRows.has(r) || zeroCols.has(c)) matrix[r][c] = 0;
}Use this when the problem asks you to rotate, transpose, or reflect the matrix in-place
Many transformation problems can be broken into simple reversible operations such as transpose, row reverse, or column reverse. This is easier than trying to map every element directly in one step.
Problem Rotate Image. First transpose the matrix, then reverse each row to get a 90 degree clockwise rotation.
// Matrix transformation — Rotate Image 90 degrees clockwise
// Step 1: Transpose, Step 2: Reverse each row
function rotate(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();
}