Tracks

Full-Stack Interview Prep

Matrix

14 problems · 16 approaches

Spiral traversal of a matrixMedium1 approach

Problem

Return all elements of an R × C matrix in spiral order: along the top row left to right, down the right column, back along the bottom row, up the left column, then repeat inward.

Example 1

Input:  [[1,2,3], [4,5,6], [7,8,9]]
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

Also asked as: Spiral traversal on a Matrix

1. Shrinking boundaries

Time O(R·C)Space O(1) extra

Keep top/bottom/left/right walls; walk right, down, left, up, moving the wall in after each pass.

function spiralOrder(m) {
  const res = [];
  let top = 0, bottom = m.length - 1, left = 0, right = m[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c++) res.push(m[top][c]);
    top++;
    for (let r = top; r <= bottom; r++) res.push(m[r][right]);
    right--;
    if (top <= bottom) { for (let c = right; c >= left; c--) res.push(m[bottom][c]); bottom--; }
    if (left <= right) { for (let r = bottom; r >= top; r--) res.push(m[r][left]); left++; }
  }
  return res;
}

Search an element in a matrixMedium2 approaches

Problem

Return true if target is in the matrix. There are two common variants: (a) each row is sorted and each row starts after the previous row ends (fully sorted in row-major order); (b) every row and every column is sorted on its own.

Example 1

Input:  [[1,3,5,7], [10,11,16,20], [23,30,34,60]], target = 3
Output: true

Also asked as: Search an element in a matriix

1. Staircase search (rows & columns sorted)

Time O(R + C)Space O(1)

Start at the top-right. If it is bigger than target move left, if smaller move down. Each step eliminates a row or column.

function searchMatrix(m, target) {
  let r = 0, c = m[0].length - 1;
  while (r < m.length && c >= 0) {
    if (m[r][c] === target) return [r, c];
    m[r][c] > target ? c-- : r++;
  }
  return null;
}

2. Binary search (fully sorted, row-major)

Time O(log(R·C))Space O(1)

Treat the R·C cells as one sorted array; map index → (row, col).

function searchMatrix(m, target) {
  const R = m.length, C = m[0].length;
  let lo = 0, hi = R * C - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    const v = m[Math.floor(mid / C)][mid % C];
    if (v === target) return true;
    v < target ? (lo = mid + 1) : (hi = mid - 1);
  }
  return false;
}

Median in a row-wise sorted matrixHard1 approach

Problem

Given an R × C matrix where each row is sorted and R × C is odd, return the median of all its elements without flattening and sorting them.

Example 1

Input:  [[1,3,5], [2,6,9], [3,6,9]]
Output: 5

Sorted: 1 2 3 3 5 6 6 9 9. The middle value is 5.

Also asked as: Find median in a row wise sorted matrix

1. Binary search on the value

Time O(R · log C · log(range))Space O(1)

For a candidate value, count how many cells are ≤ it (binary search per row). The median is the smallest value with count ≥ (R·C+1)/2.

function matrixMedian(m) {
  const R = m.length, C = m[0].length, need = (R * C + 1) >> 1;
  let lo = Math.min(...m.map((row) => row[0]));
  let hi = Math.max(...m.map((row) => row[C - 1]));
  const countLE = (x) => m.reduce((acc, row) => {
    let l = 0, r = C;
    while (l < r) { const mid = (l + r) >> 1; row[mid] <= x ? (l = mid + 1) : (r = mid); }
    return acc + l;
  }, 0);
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    countLE(mid) < need ? (lo = mid + 1) : (hi = mid);
  }
  return lo;
}

Row with the maximum number of 1sEasy1 approach

Problem

In a binary matrix whose rows are sorted (all 0s, then all 1s), return the index of the first row with the most 1s, or −1 if the matrix has no 1s.

Example 1

Input:  [[0,1,1,1], [0,0,1,1], [1,1,1,1], [0,0,0,0]]
Output: 2

Also asked as: Find row with maximum no. of 1's

1. Staircase from top-right

Time O(R + C)Space O(1)

Each row is sorted (0s then 1s). Move left while the current cell is 1; every time you can, that row has more 1s.

function rowWithMostOnes(m) {
  let best = -1, c = m[0].length - 1;
  for (let r = 0; r < m.length; r++) {
    while (c >= 0 && m[r][c] === 1) { c--; best = r; }
  }
  return best;
}

Print elements in sorted order (row- and column-sorted matrix)Medium1 approach

Problem

Every row and every column of an n × n matrix is sorted. Print all its elements in sorted order.

Example 1

Input:  [[10,20,30,40], [15,25,35,45], [27,29,37,48], [32,33,39,50]]
Output: 10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50

Also asked as: Print elements in sorted order using row-column wise sorted matrix

1. Min-heap of row frontiers (merge k sorted lists)

Time O(R·C · log R)Space O(R)

Each row is sorted; push the first cell of every row into a min-heap, pop the smallest, and push the next cell from that row.

function sortedOrder(m) {
  const heap = m.map((row, r) => [row[0], r, 0]);
  heap.sort((a, b) => a[0] - b[0]);
  const out = [];
  while (heap.length) {
    const [val, r, c] = heap.shift();
    out.push(val);
    if (c + 1 < m[r].length) {
      const next = [m[r][c + 1], r, c + 1];
      let i = heap.findIndex((x) => x[0] > next[0]);
      i === -1 ? heap.push(next) : heap.splice(i, 0, next);
    }
  }
  return out;
}

Shown with a sorted array for brevity; a real binary min-heap makes each push/pop O(log R).

Maximum size rectangle of 1s in a binary matrixHard1 approach

Problem

Return the area of the largest rectangle that contains only 1s in a binary matrix.

Example 1

Input:  [[0,1,1,0], [1,1,1,1], [1,1,1,1], [1,1,0,0]]
Output: 8

Rows 1–2, all four columns.

Also asked as: Maximum size rectangle

1. Row-by-row histogram + largest rectangle in histogram

Time O(R·C)Space O(C)

For each row, build a histogram of consecutive 1s upward, then run the O(n) stack-based "largest rectangle in histogram" on it.

function maximalRectangle(m) {
  const C = m[0].length;
  const heights = Array(C).fill(0);
  let best = 0;
  for (const row of m) {
    for (let c = 0; c < C; c++) heights[c] = row[c] ? heights[c] + 1 : 0;
    best = Math.max(best, largestInHistogram(heights));
  }
  return best;
}
function largestInHistogram(h) {
  const st = [];
  let best = 0;
  for (let i = 0; i <= h.length; i++) {
    const cur = i === h.length ? 0 : h[i];
    while (st.length && h[st[st.length - 1]] >= cur) {
      const height = h[st.pop()];
      const width = st.length ? i - st[st.length - 1] - 1 : i;
      best = Math.max(best, height * width);
    }
    st.push(i);
  }
  return best;
}

Maximum value of a[c][d] − a[a][b] with c > a and d > bMedium1 approach

Problem

In an n × n matrix, return the maximum of mat[c][d] − mat[a][b] over all index choices where c > a and d > b. The second cell must be strictly below and strictly to the right of the first. Aim for O(n²).

Example 1

Input:  [[1,2,-1,-4,-20], [-8,-3,4,2,1], [3,8,6,1,3], [-4,-1,1,7,-6], [0,-4,10,-5,1]]
Output: 18

mat[4][2] − mat[1][0] = 10 − (−8).

Also asked as: Find a specific pair in matrix

1. Suffix max of the bottom-right submatrix

Time O(n²)Space O(n²)

maxFromBelowRight[i][j] = max over the submatrix below and right of (i,j). Answer = max(maxFromBelowRight[i+1][j+1] − a[i][j]).

function maxDiff(a) {
  const n = a.length;
  const suf = Array.from({ length: n + 1 }, () => Array(n + 1).fill(-Infinity));
  let ans = -Infinity;
  for (let i = n - 1; i >= 0; i--)
    for (let j = n - 1; j >= 0; j--) {
      suf[i][j] = Math.max(a[i][j], suf[i + 1][j], suf[i][j + 1]);
      if (i + 1 < n && j + 1 < n) ans = Math.max(ans, suf[i + 1][j + 1] - a[i][j]);
    }
  return ans;
}

Rotate a matrix by 90 degreesMedium1 approach

Problem

Rotate an n × n matrix by 90 degrees clockwise, in place.

Example 1

Input:  [[1,2,3], [4,5,6], [7,8,9]]
Output: [[7,4,1], [8,5,2], [9,6,3]]

Also asked as: Rotate matrix by 90 degrees

1. Transpose, then reverse each row

Time O(n²)Space O(1)

Transposing swaps rows/columns; reversing each row then gives a clockwise 90° rotation. In place.

function rotate(m) {
  const n = m.length;
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j < n; j++)
      [m[i][j], m[j][i]] = [m[j][i], m[i][j]];
  for (const row of m) row.reverse();
  return m;
}

Counter-clockwise: reverse each row first, then transpose (or reverse the row order after transpose).

Kth smallest element in a row- and column-sorted matrixMedium1 approach

Problem

Every row and every column of an n × n matrix is sorted in ascending order. Return the kth smallest element overall, counting duplicates.

Example 1

Input:  matrix = [[1,5,9], [10,11,13], [12,13,15]], k = 8
Output: 13

Also asked as: Kth smallest element in a row-cpumn wise sorted matrix

1. Binary search on the value

Time O(n · log(range))Space O(1)

Count cells ≤ mid with a staircase walk (O(n)). The answer is the smallest value whose count ≥ k.

function kthSmallest(m, k) {
  const n = m.length;
  let lo = m[0][0], hi = m[n - 1][n - 1];
  const countLE = (x) => {
    let cnt = 0, r = n - 1, c = 0;
    while (r >= 0 && c < n) {
      if (m[r][c] <= x) { cnt += r + 1; c++; }
      else r--;
    }
    return cnt;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    countLE(mid) < k ? (lo = mid + 1) : (hi = mid);
  }
  return lo;
}

Common elements in all rows of a matrixMedium1 approach

Problem

Return the distinct values that appear in every row of the matrix. The rows are not sorted.

Example 1

Input:  [[1,2,1,4,8], [3,7,8,5,1], [8,7,7,3,1], [8,1,2,7,9]]
Output: [1, 8]

Also asked as: Common elements in all rows of a given matrix

1. Frequency map seeded by the first row

Time O(R·C)Space O(C)

Put row 0 in a map (value → 1). For each later row, bump a value only if its stored count equals the current row index. At the end, values with count === R are common to all.

function commonInAllRows(m) {
  const R = m.length;
  const cnt = new Map();
  for (const v of m[0]) cnt.set(v, 1);
  for (let r = 1; r < R; r++)
    for (const v of m[r])
      if (cnt.get(v) === r) cnt.set(v, r + 1);
  return [...cnt].filter(([, c]) => c === R).map(([v]) => v);
}

Valid SudokuMedium1 approach

Problem

Given a partially filled 9 × 9 board ("." for empty), return true if the filled cells break no rule: no repeated digit in any row, any column, or any of the nine 3 × 3 boxes. The board does not need to be solvable.

Example 1

Input:  a board where one row contains two 8s
Output: false

1. One pass with sets per row, column and box

Time O(81) = O(1)Space O(1)

Box index is floor(r/3)*3 + floor(c/3). Reject a digit already seen in any of its three units.

function isValidSudoku(board) {
  const rows = Array.from({ length: 9 }, () => new Set());
  const cols = Array.from({ length: 9 }, () => new Set());
  const boxes = Array.from({ length: 9 }, () => new Set());
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const v = board[r][c];
      if (v === '.') continue;
      const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
      if (rows[r].has(v) || cols[c].has(v) || boxes[b].has(v)) return false;
      rows[r].add(v); cols[c].add(v); boxes[b].add(v);
    }
  }
  return true;
}

Range Sum Query 2D – ImmutableMedium1 approach

Problem

Given a fixed matrix, answer many queries sumRegion(r1, c1, r2, c2) — the sum of the rectangle with top-left (r1, c1) and bottom-right (r2, c2) — each in O(1).

Example 1

Input:  matrix = [[3,0,1,4,2], [5,6,3,2,1], [1,2,0,1,5], [4,1,0,1,7], [1,0,3,0,5]]; sumRegion(2,1,4,3)
Output: 8

1. 2-D prefix sums (inclusion–exclusion)

Time O(R·C) build, O(1) per querySpace O(R·C)

P[r+1][c+1] = sum of the rectangle (0,0)..(r,c). A query adds the big rectangle, subtracts the strips above and left, and adds back the doubly-removed corner.

class NumMatrix {
  constructor(m) {
    const R = m.length, C = m[0].length;
    this.P = Array.from({ length: R + 1 }, () => new Array(C + 1).fill(0));
    for (let r = 0; r < R; r++)
      for (let c = 0; c < C; c++)
        this.P[r + 1][c + 1] = m[r][c] + this.P[r][c + 1] + this.P[r + 1][c] - this.P[r][c];
  }
  sumRegion(r1, c1, r2, c2) {
    const P = this.P;
    return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
  }
}

Set Matrix ZeroesMedium2 approaches

Problem

If a cell is 0, set its entire row and column to 0. Do it in place; the follow-up asks for O(1) extra space.

Example 1

Input:  [[1,1,1], [1,0,1], [1,1,1]]
Output: [[1,0,1], [0,0,0], [1,0,1]]

1. Row and column sets

Time O(R·C)Space O(R + C)

Record which rows and columns contain a zero, then zero them.

function setZeroes(m) {
  const rows = new Set(), cols = new Set();
  m.forEach((row, r) => row.forEach((v, c) => { if (v === 0) { rows.add(r); cols.add(c); } }));
  m.forEach((row, r) => row.forEach((_, c) => { if (rows.has(r) || cols.has(c)) row[c] = 0; }));
}

2. First row and column as markers

Time O(R·C)Space O(1)

Use row 0 and column 0 as the flags. Remember separately whether row 0 / column 0 themselves had a zero, and zero them last.

function setZeroes(m) {
  const R = m.length, C = m[0].length;
  const row0 = m[0].includes(0), col0 = m.some((row) => row[0] === 0);
  for (let r = 1; r < R; r++)
    for (let c = 1; c < C; c++)
      if (m[r][c] === 0) { m[r][0] = 0; m[0][c] = 0; }
  for (let r = 1; r < R; r++)
    for (let c = 1; c < C; c++)
      if (m[r][0] === 0 || m[0][c] === 0) m[r][c] = 0;
  if (row0) m[0].fill(0);
  if (col0) for (let r = 0; r < R; r++) m[r][0] = 0;
}

Game of LifeMedium1 approach

Problem

Each cell is live (1) or dead (0). All cells update at the same time: a live cell with 2 or 3 live neighbours (out of 8) survives, otherwise it dies; a dead cell with exactly 3 live neighbours becomes live. Compute the next state in place.

Example 1

Input:  [[0,1,0], [0,0,1], [1,1,1], [0,0,0]]
Output: [[0,0,0], [1,0,1], [0,1,1], [0,1,0]]

1. In place with bit encoding

Time O(R·C)Space O(1)

Bit 0 holds the current state, bit 1 the next. Count live neighbours using (v & 1), write the next state into bit 1, then shift every cell right.

function gameOfLife(b) {
  const R = b.length, C = b[0].length;
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      let live = 0;
      for (let dr = -1; dr <= 1; dr++)
        for (let dc = -1; dc <= 1; dc++) {
          if (!dr && !dc) continue;
          const nr = r + dr, nc = c + dc;
          if (nr >= 0 && nc >= 0 && nr < R && nc < C) live += b[nr][nc] & 1;
        }
      if (live === 3 || (live === 2 && (b[r][c] & 1))) b[r][c] |= 2;
    }
  }
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) b[r][c] >>= 1;
}