Matrix Problems

Matrix problems are a rich collection of classic algorithms tested heavily in interviews. Each has a specific technique: spiral traversal uses boundary pointers, rotation uses transpose + reverse, flood-fill uses DFS/BFS, and in-place tricks use the matrix itself as storage to achieve O(1) extra space.

Spiral Order Traversal

Traverse an m×n matrix in spiral order (clockwise from the outside in).

Technique: Maintain four boundaries: top, bottom, left, right. Traverse each layer of the spiral by walking along the four edges, then shrink boundaries.

// Spiral Matrix — O(m·n) time, O(1) extra space
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) {
    // Walk right along top row
    for (let c = left; c <= right; c++) result.push(matrix[top][c]);
    top++;

    // Walk down along right column
    for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);
    right--;

    // Walk left along bottom row (if still valid)
    if (top <= bottom) {
      for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);
      bottom--;
    }

    // Walk up along left column (if still valid)
    if (left <= right) {
      for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);
      left++;
    }
  }

  return result;
}

const m = [[1,2,3],[4,5,6],[7,8,9]];
console.log(spiralOrder(m));
// [1,2,3,6,9,8,7,4,5]

Rotate Matrix 90° In-Place

Rotate an n×n matrix 90 degrees clockwise in-place, using no extra matrix.

Key insight: Clockwise 90° rotation = transpose then reverse each row.

Transpose: swap matrix[i][j] with matrix[j][i]
Reverse each row: reverse the elements left to right

// Rotate Matrix 90° Clockwise — O(n²) time, O(1) space
function rotate(matrix) {
  const n = matrix.length;

  // Step 1: Transpose (swap across main 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;
}

// Counter-clockwise 90°: reverse each row THEN transpose
function rotateCounterCW(matrix) {
  matrix.forEach(row => row.reverse());
  const n = matrix.length;
  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]];
  return matrix;
}

const mat = [[1,2,3],[4,5,6],[7,8,9]];
console.log(rotate(mat));
// [[7,4,1],[8,5,2],[9,6,3]]

Note

The transpose-then-reverse trick works because a 90° clockwise rotation maps (i, j) to (j, n-1-i). Transpose maps (i,j) to (j,i), and reversing each row maps (j,i) to (j, n-1-i). Combined: (i,j) → (j, n-1-i).

Set Matrix Zeroes — O(1) Space

If any element in a matrix is 0, set its entire row and column to 0.

Naive: use two extra O(m+n) sets to record which rows/cols to zero out. O(1) trick: use the first row and first column of the matrix itself as flags.

// Set Matrix Zeroes — O(m·n) time, O(1) space
function setZeroes(matrix) {
  const m = matrix.length, n = matrix[0].length;
  let firstRowZero = false;
  let firstColZero = false;

  // Check if first row or first col originally has a zero
  for (let c = 0; c < n; c++) if (matrix[0][c] === 0) firstRowZero = true;
  for (let r = 0; r < m; r++) if (matrix[r][0] === 0) firstColZero = true;

  // Use first row/col as flags for the rest of the matrix
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      if (matrix[r][c] === 0) {
        matrix[r][0] = 0;  // mark this row
        matrix[0][c] = 0;  // mark this column
      }
    }
  }

  // Zero out cells based on flags
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      if (matrix[r][0] === 0 || matrix[0][c] === 0) {
        matrix[r][c] = 0;
      }
    }
  }

  // Zero out first row and column if originally had zeros
  if (firstRowZero) for (let c = 0; c < n; c++) matrix[0][c] = 0;
  if (firstColZero) for (let r = 0; r < m; r++) matrix[r][0] = 0;
}

const z = [[1,1,1],[1,0,1],[1,1,1]];
setZeroes(z);
console.log(z); // [[1,0,1],[0,0,0],[1,0,1]]

Warning

The O(1) trick requires processing the first row and column LAST, because they are used as flags during the main pass. Zeroing them out before the main pass would corrupt the flags and give wrong results.

Number of Islands — DFS/BFS

Count the number of islands in a grid (connected groups of '1's surrounded by '0's or edges).

DFS approach: When you find a '1', DFS to mark all connected '1's as visited, then increment the island count.

// Number of Islands — O(m·n) time
function numIslands(grid) {
  if (!grid.length) return 0;
  const m = grid.length, n = grid[0].length;
  let islands = 0;

  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== '1') return;
    grid[r][c] = '0';  // mark visited (flood fill)
    dfs(r + 1, c); dfs(r - 1, c);
    dfs(r, c + 1); dfs(r, c - 1);
  }

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') {
        islands++;
        dfs(r, c);  // flood fill this island
      }
    }
  }

  return islands;
}

const grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
];
console.log(numIslands(grid)); // 3

Flood Fill

Starting from a source cell, change all connected cells of the same color to a new color. This is the "paint bucket" operation used in image editors.

// Flood Fill — O(m·n) time
function floodFill(image, sr, sc, color) {
  const originalColor = image[sr][sc];
  if (originalColor === color) return image;  // no-op to avoid infinite loop

  function dfs(r, c) {
    if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return;
    if (image[r][c] !== originalColor) return;

    image[r][c] = color;  // paint
    dfs(r + 1, c); dfs(r - 1, c);
    dfs(r, c + 1); dfs(r, c - 1);
  }

  dfs(sr, sc);
  return image;
}

console.log(floodFill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2));
// [[2,2,2],[2,2,0],[2,0,1]]

Surrounded Regions

Capture all regions of 'O's surrounded by 'X's (not connected to the border). Border-connected 'O's cannot be captured.

Trick: Mark border-connected 'O's as safe (use a temporary marker), then flip all remaining 'O's to 'X', then restore the markers.

// Surrounded Regions — O(m·n) time
function solve(board) {
  const m = board.length, n = board[0].length;

  // DFS to mark border-connected 'O's as safe
  function markSafe(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== 'O') return;
    board[r][c] = 'S';  // temporary safe marker
    markSafe(r + 1, c); markSafe(r - 1, c);
    markSafe(r, c + 1); markSafe(r, c - 1);
  }

  // Mark all border 'O's and their connected regions as safe
  for (let r = 0; r < m; r++) {
    if (board[r][0] === 'O') markSafe(r, 0);
    if (board[r][n-1] === 'O') markSafe(r, n-1);
  }
  for (let c = 0; c < n; c++) {
    if (board[0][c] === 'O') markSafe(0, c);
    if (board[m-1][c] === 'O') markSafe(m-1, c);
  }

  // Flip: 'O' → 'X' (captured), 'S' → 'O' (safe, restore)
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (board[r][c] === 'O') board[r][c] = 'X';
      else if (board[r][c] === 'S') board[r][c] = 'O';
    }
  }
}

const b = [['X','X','X','X'],['X','O','O','X'],['X','X','O','X'],['X','O','X','X']];
solve(b);
console.log(b[1][1]); // 'X' — captured
console.log(b[3][1]); // 'O' — border-connected

Word Search

Covered in the Backtracking chapter, but the matrix context is worth reiterating. DFS from each cell, marking visited cells to avoid reuse, then restoring after each path.

// Word Search — O(m·n·4^L) where L = word length
function exist(board, word) {
  const m = board.length, n = board[0].length;

  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[idx]) return false;

    const temp = board[r][c];
    board[r][c] = '#';
    const found = dfs(r+1,c,idx+1) || dfs(r-1,c,idx+1) ||
                  dfs(r,c+1,idx+1) || dfs(r,c-1,idx+1);
    board[r][c] = temp;
    return found;
  }

  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (dfs(r, c, 0)) return true;

  return false;
}

Game of Life — In-Place Encoding

Update a Game of Life board in-place: dead=0, alive=1. Each cell's next state depends on the count of its current live neighbors.

Rules: Live cell with 2 or 3 neighbors survives; dead cell with 3 neighbors becomes alive; everything else dies.

O(1) space trick: Encode both current and next states in one integer. Use 2 bits per cell: bit 0 = current state, bit 1 = next state.

// Game of Life — O(m·n) time, O(1) space
function gameOfLife(board) {
  const m = board.length, n = board[0].length;
  const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      let liveNeighbors = 0;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
          // board[nr][nc] & 1 reads the ORIGINAL state (bit 0)
          liveNeighbors += board[nr][nc] & 1;
        }
      }

      const isAlive = board[r][c] & 1;
      let nextState = 0;

      if (isAlive && (liveNeighbors === 2 || liveNeighbors === 3)) {
        nextState = 1;  // survives
      } else if (!isAlive && liveNeighbors === 3) {
        nextState = 1;  // born
      }

      // Store next state in bit 1 (shift left by 1)
      board[r][c] |= nextState << 1;
    }
  }

  // Extract next state (shift right by 1)
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      board[r][c] >>= 1;
}

const gol = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]];
gameOfLife(gol);
console.log(gol);
// [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Tip

The bit encoding trick `board[r][c] |= nextState << 1` works because we only need 2 bits of information per cell: old state (bit 0) and new state (bit 1). Reading `board[r][c] & 1` always gives the original value, even after we've updated other cells.

Matrix Problem Techniques Summary

Problem	Technique	Space	Time
Spiral Order	Boundary pointers (top/bottom/left/right)	O(1)	O(m·n)
Rotate 90°	Transpose + reverse rows	O(1)	O(n²)
Set Zeroes	First row/col as flags	O(1)	O(m·n)
Number of Islands	DFS flood fill	O(m·n) stack	O(m·n)
Flood Fill	DFS from source	O(m·n) stack	O(m·n)
Surrounded Regions	Mark safe from border + flip	O(m·n) stack	O(m·n)
Word Search	DFS + in-place visited mark	O(L)	O(m·n·4^L)
Game of Life	2-bit encoding (old in bit 0, new in bit 1)	O(1)	O(m·n)

Most matrix DFS problems mark cells visited by mutating the cell (e.g., set to 0 or #)
Always restore the cell after DFS if the mutation must be undone (Word Search)
The O(1) space tricks (Set Zeroes, Game of Life) exploit unused bits in the cell value
Surrounded Regions: the key insight is that only border-connected O cells are safe
For rotation and transpose, always verify with a small 3×3 example before coding