Matrix Problems - Complete Guide

Matrix problems involve 2D arrays and grids. This guide covers traversal patterns, transformations, and common algorithms for matrix-based challenges.

Matrix Basics #

// Create matrix
const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

// Access element
const val = matrix[row][col];

// Dimensions
const rows = matrix.length;
const cols = matrix[0].length;

// Iterate
for (let i = 0; i < rows; i++) {
  for (let j = 0; j < cols; j++) {
    console.log(matrix[i][j]);
  }
}

Matrix Traversal #

Spiral Order #

function spiralOrder(matrix) {
  if (matrix.length === 0) return [];

  const result = [];
  let top = 0;
  let bottom = matrix.length - 1;
  let left = 0;
  let right = matrix[0].length - 1;

  while (top <= bottom && left <= right) {
    // Right
    for (let col = left; col <= right; col++) {
      result.push(matrix[top][col]);
    }
    top++;

    // Down
    for (let row = top; row <= bottom; row++) {
      result.push(matrix[row][right]);
    }
    right--;

    // Left
    if (top <= bottom) {
      for (let col = right; col >= left; col--) {
        result.push(matrix[bottom][col]);
      }
      bottom--;
    }

    // Up
    if (left <= right) {
      for (let row = bottom; row >= top; row--) {
        result.push(matrix[row][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]

Spiral Matrix II #

Generate spiral matrix.

function generateMatrix(n) {
  const matrix = Array(n).fill(0).map(() => Array(n).fill(0));
  let top = 0;
  let bottom = n - 1;
  let left = 0;
  let right = n - 1;
  let num = 1;

  while (top <= bottom && left <= right) {
    // Right
    for (let col = left; col <= right; col++) {
      matrix[top][col] = num++;
    }
    top++;

    // Down
    for (let row = top; row <= bottom; row++) {
      matrix[row][right] = num++;
    }
    right--;

    // Left
    for (let col = right; col >= left; col--) {
      matrix[bottom][col] = num++;
    }
    bottom--;

    // Up
    for (let row = bottom; row >= top; row--) {
      matrix[row][left] = num++;
    }
    left++;
  }

  return matrix;
}

console.log(generateMatrix(3));
// [[1, 2, 3], [8, 9, 4], [7, 6, 5]]

Diagonal Traverse #

function findDiagonalOrder(matrix) {
  if (matrix.length === 0) return [];

  const rows = matrix.length;
  const cols = matrix[0].length;
  const result = [];
  let row = 0;
  let col = 0;
  let direction = 1;  // 1 = up-right, -1 = down-left

  while (result.length < rows * cols) {
    result.push(matrix[row][col]);

    if (direction === 1) {
      // Going up-right
      if (col === cols - 1) {
        row++;
        direction = -1;
      } else if (row === 0) {
        col++;
        direction = -1;
      } else {
        row--;
        col++;
      }
    } else {
      // Going down-left
      if (row === rows - 1) {
        col++;
        direction = 1;
      } else if (col === 0) {
        row++;
        direction = 1;
      } else {
        row++;
        col--;
      }
    }
  }

  return result;
}

console.log(findDiagonalOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]));
// [1, 2, 4, 7, 5, 3, 6, 8, 9]

Matrix Transformation #

Rotate Image #

Rotate 90 degrees clockwise.

function rotate(matrix) {
  const n = matrix.length;

  // Transpose
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }

  // Reverse each row
  for (let i = 0; i < n; i++) {
    matrix[i].reverse();
  }

  return matrix;
}

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

Transpose Matrix #

function transpose(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const result = Array(cols).fill(0).map(() => Array(rows));

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      result[j][i] = matrix[i][j];
    }
  }

  return result;
}

console.log(transpose([[1, 2, 3], [4, 5, 6]]));
// [[1, 4], [2, 5], [3, 6]]

Set Matrix Zeroes #

function setZeroes(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let firstRowZero = false;
  let firstColZero = false;

  // Check first row
  for (let j = 0; j < cols; j++) {
    if (matrix[0][j] === 0) {
      firstRowZero = true;
      break;
    }
  }

  // Check first column
  for (let i = 0; i < rows; i++) {
    if (matrix[i][0] === 0) {
      firstColZero = true;
      break;
    }
  }

  // Use first row/col as markers
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (matrix[i][j] === 0) {
        matrix[i][0] = 0;
        matrix[0][j] = 0;
      }
    }
  }

  // Set zeros based on markers
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (matrix[i][0] === 0 || matrix[0][j] === 0) {
        matrix[i][j] = 0;
      }
    }
  }

  // Set first row/col if needed
  if (firstRowZero) {
    for (let j = 0; j < cols; j++) {
      matrix[0][j] = 0;
    }
  }

  if (firstColZero) {
    for (let i = 0; i < rows; i++) {
      matrix[i][0] = 0;
    }
  }

  return matrix;
}

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

Search 2D Matrix #

Sorted rows and columns.

function searchMatrix(matrix, target) {
  if (matrix.length === 0) return false;

  const rows = matrix.length;
  const cols = matrix[0].length;

  // Binary search treating as 1D array
  let left = 0;
  let right = rows * cols - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const row = Math.floor(mid / cols);
    const col = mid % cols;
    const val = matrix[row][col];

    if (val === target) {
      return true;
    } else if (val < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return false;
}

const matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]];
console.log(searchMatrix(matrix, 3));   // true
console.log(searchMatrix(matrix, 13));  // false

Search 2D Matrix II #

Each row/column sorted independently.

function searchMatrix(matrix, target) {
  if (matrix.length === 0) return false;

  const rows = matrix.length;
  const cols = matrix[0].length;

  // Start from top-right
  let row = 0;
  let col = cols - 1;

  while (row < rows && col >= 0) {
    const val = matrix[row][col];

    if (val === target) {
      return true;
    } else if (val > target) {
      col--;  // Move left
    } else {
      row++;  // Move down
    }
  }

  return false;
}

const matrix = [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
];

console.log(searchMatrix(matrix, 5));   // true
console.log(searchMatrix(matrix, 20));  // false

Island Problems #

Number of Islands #

function numIslands(grid) {
  if (grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(i, j) {
    if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] === '0') {
      return;
    }

    grid[i][j] = '0';  // Mark visited

    dfs(i + 1, j);  // Down
    dfs(i - 1, j);  // Up
    dfs(i, j + 1);  // Right
    dfs(i, j - 1);  // Left
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === '1') {
        count++;
        dfs(i, j);
      }
    }
  }

  return count;
}

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

Max Area of Island #

function maxAreaOfIsland(grid) {
  if (grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let maxArea = 0;

  function dfs(i, j) {
    if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] === 0) {
      return 0;
    }

    grid[i][j] = 0;

    return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1);
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 1) {
        maxArea = Math.max(maxArea, dfs(i, j));
      }
    }
  }

  return maxArea;
}

const grid = [
  [0, 0, 1, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 1, 0, 0, 0],
  [1, 1, 0, 0, 1]
];

console.log(maxAreaOfIsland(grid));  // 6

Surrounded Regions #

function solve(board) {
  if (board.length === 0) return;

  const rows = board.length;
  const cols = board[0].length;

  function dfs(i, j) {
    if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] !== 'O') {
      return;
    }

    board[i][j] = 'T';  // Temporary mark

    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
  }

  // Mark border-connected 'O's
  for (let i = 0; i < rows; i++) {
    dfs(i, 0);
    dfs(i, cols - 1);
  }

  for (let j = 0; j < cols; j++) {
    dfs(0, j);
    dfs(rows - 1, j);
  }

  // Flip remaining 'O's to 'X' and 'T's back to 'O'
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (board[i][j] === 'O') {
        board[i][j] = 'X';
      } else if (board[i][j] === 'T') {
        board[i][j] = 'O';
      }
    }
  }
}

const board = [
  ['X', 'X', 'X', 'X'],
  ['X', 'O', 'O', 'X'],
  ['X', 'X', 'O', 'X'],
  ['X', 'O', 'X', 'X']
];

solve(board);
console.log(board);
// [['X','X','X','X'],['X','X','X','X'],['X','X','X','X'],['X','O','X','X']]

function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;

  function dfs(i, j, index) {
    if (index === word.length) return true;

    if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] !== word[index]) {
      return false;
    }

    const temp = board[i][j];
    board[i][j] = '#';  // Mark visited

    const found = dfs(i + 1, j, index + 1) ||
                  dfs(i - 1, j, index + 1) ||
                  dfs(i, j + 1, index + 1) ||
                  dfs(i, j - 1, index + 1);

    board[i][j] = temp;  // Restore

    return found;
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (dfs(i, j, 0)) {
        return true;
      }
    }
  }

  return false;
}

const board = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E']
];

console.log(exist(board, 'ABCCED'));  // true
console.log(exist(board, 'SEE'));     // true
console.log(exist(board, 'ABCB'));    // false

Shortest Path #

Shortest Path in Binary Matrix #

function shortestPathBinaryMatrix(grid) {
  const n = grid.length;

  if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) {
    return -1;
  }

  const directions = [
    [-1, -1], [-1, 0], [-1, 1],
    [0, -1],           [0, 1],
    [1, -1],  [1, 0],  [1, 1]
  ];

  const queue = [[0, 0, 1]];  // [row, col, distance]
  grid[0][0] = 1;  // Mark visited

  while (queue.length > 0) {
    const [row, col, dist] = queue.shift();

    if (row === n - 1 && col === n - 1) {
      return dist;
    }

    for (const [dr, dc] of directions) {
      const newRow = row + dr;
      const newCol = col + dc;

      if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && grid[newRow][newCol] === 0) {
        queue.push([newRow, newCol, dist + 1]);
        grid[newRow][newCol] = 1;
      }
    }
  }

  return -1;
}

const grid = [[0, 1], [1, 0]];
console.log(shortestPathBinaryMatrix(grid));  // 2

Valid Sudoku #

function isValidSudoku(board) {
  const rows = Array(9).fill(0).map(() => new Set());
  const cols = Array(9).fill(0).map(() => new Set());
  const boxes = Array(9).fill(0).map(() => new Set());

  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const val = board[i][j];

      if (val === '.') continue;

      const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);

      if (rows[i].has(val) || cols[j].has(val) || boxes[boxIndex].has(val)) {
        return false;
      }

      rows[i].add(val);
      cols[j].add(val);
      boxes[boxIndex].add(val);
    }
  }

  return true;
}

Game of Life #

function gameOfLife(board) {
  const rows = board.length;
  const cols = board[0].length;

  const directions = [
    [-1, -1], [-1, 0], [-1, 1],
    [0, -1],           [0, 1],
    [1, -1],  [1, 0],  [1, 1]
  ];

  function countNeighbors(i, j) {
    let count = 0;

    for (const [di, dj] of directions) {
      const ni = i + di;
      const nj = j + dj;

      if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && Math.abs(board[ni][nj]) === 1) {
        count++;
      }
    }

    return count;
  }

  // Use 2 for dead->live, -1 for live->dead
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      const neighbors = countNeighbors(i, j);

      if (board[i][j] === 1) {
        if (neighbors < 2 || neighbors > 3) {
          board[i][j] = -1;
        }
      } else {
        if (neighbors === 3) {
          board[i][j] = 2;
        }
      }
    }
  }

  // Update to final state
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (board[i][j] > 0) {
        board[i][j] = 1;
      } else {
        board[i][j] = 0;
      }
    }
  }
}

Time Complexity #

ProblemTime ComplexitySpace Complexity
Spiral OrderO(m×n)O(1)
RotateO(n²)O(1)
Set ZeroesO(m×n)O(1)
SearchO(log(m×n))O(1)
DFS/BFSO(m×n)O(m×n)

Best Practices #

  1. Check boundaries - Avoid index out of bounds
  2. Use directions array - For neighbor traversal
  3. Mark visited - Modify in-place or use visited set
  4. Handle edge cases - Empty matrix, single element
  5. DFS vs BFS - DFS for paths, BFS for shortest
  6. Space optimization - Reuse first row/column for markers
  7. Clone when needed - Don’t modify input if required

Matrix problems are fundamental for grid-based algorithms. Master these patterns for efficient 2D array manipulation.

Previous Stacks and Queues - Complete Guide Recursion - Complete Guide for Beginners Next