Matrix problems

Grids in JavaScript: indexing, building, and the shared-row trap

A matrix is an array of row arrays, so matrix[r][c] reads row r, column c, and the first index is always the vertical one. Take the sizes from the data and guard the empty case: rows = matrix.length, cols = matrix[0].length throws on [], so return early when there are no rows. Four small facts get reused in almost every problem below.

• Flat index. Cell (r, c) is number r * cols + c in row-major order, and number id sits at r = Math.floor(id / cols), c = id % cols. This turns any grid into a 1D array for binary search or hashing.
• Diagonals. On a main-direction diagonal (down and to the right) r - c never changes; on an anti-diagonal (down and to the left) r + c never changes. Both are ready-made keys for "group the cells on the same diagonal".
• Neighbours. Keep the four moves in one table, const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]], loop over it, and test the bounds 0 <= nr < rows and 0 <= nc < cols before reading. Add four diagonal moves for the eight-neighbour version.
• Building a blank grid. Write Array.from({ length: rows }, () => new Array(cols).fill(0)).

Traversal direction — the pattern behind spiral order

function spiralOrder(matrix) {
  if (matrix.length === 0) return [];
  const result = [];
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;

  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c++) result.push(matrix[top][c]);
    top++;
    for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);
    right--;
    if (top <= bottom) { // guard: this row may already be consumed
      for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);
      bottom--;
    }
    if (left <= right) { // guard: this column may already be consumed
      for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);
      left++;
    }
  }
  return result;
}

Dry run: spiralOrder on the 3×4 grid in the figure above

After pass 2, top becomes 2 while bottom is still 1 — the while loop's own condition (top <= bottom) catches that and stops. Inside the pass, the bottom-row guard had already skipped the redundant walk, while the left-column guard was still true (left == right == 1) and its loop simply ran zero times. The checks protect against the same non-square edge case from different angles.

Direction arrays: turning right with a table

The four-boundary spiral needs guards because the boundaries can cross. A second formulation has no boundaries at all: walk in the current direction, and turn right whenever the next cell is off the grid or already filled. "Turn right" is just advancing an index in a table of moves ordered right, down, left, up.

function generateMatrix(n) { // Spiral Matrix II: fill an n x n grid with 1..n*n in spiral order
  const grid = Array.from({ length: n }, () => new Array(n).fill(0));
  const dr = [0, 1, 0, -1];
  const dc = [1, 0, -1, 0];
  let r = 0, c = 0, d = 0; // start top-left, heading right

  for (let value = 1; value <= n * n; value++) {
    grid[r][c] = value;
    const nr = r + dr[d], nc = c + dc[d];
    if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] !== 0) {
      d = (d + 1) % 4; // blocked: turn right, then step in the new direction
    }
    r += dr[d];
    c += dc[d];
  }
  return grid;
}

Dry run: generateMatrix(3)

The result is [[1,2,3],[8,9,4],[7,6,5]]. This is O(n²) time, one step per cell, and it uses the grid itself as the "visited" record (a 0 means unwritten). When you read a matrix in spiral order instead of generating one, the grid already holds data, so the same loop needs a separate seen array or a sentinel value you will not confuse with real data. Pick the boundary version when the shape is a plain rectangle and the direction table when the path has to react to obstacles.

Diagonals: r + c names each anti-diagonal

"Diagonal Traverse" asks for every element, one anti-diagonal at a time, alternating direction. Every cell on the diagonal with sum s satisfies c = s - r, and the sums run from 0 to rows + cols - 2. For each sum, collect the cells in order of increasing row, then reverse every other diagonal. The only fiddly part is the range of rows that lie inside the grid: r must be at least s - (cols - 1) so that c does not pass the right edge, and at most min(rows - 1, s).

function findDiagonalOrder(mat) {
  const rows = mat.length, cols = mat[0].length;
  const out = [];
  for (let s = 0; s <= rows + cols - 2; s++) {
    const diagonal = [];
    const first = Math.max(0, s - cols + 1);
    const last = Math.min(rows - 1, s);
    for (let r = first; r <= last; r++) diagonal.push(mat[r][s - r]);
    if (s % 2 === 0) diagonal.reverse(); // even sums are walked bottom-left to top-right
    out.push(...diagonal);
  }
  return out;
}

On [[1,2,3],[4,5,6],[7,8,9]] the output is 1 2 4 7 5 3 6 8 9. Time O(rows · cols), and the temporary diagonal array is O(min(rows, cols)). This grouping idea is the same one that makes Toeplitz checks and "sort each diagonal" problems easy: use r - c (or r + c) as the key and let the key do the diagonal bookkeeping.

In-place rotation — 90° with no extra matrix

Rotating 90° clockwise decomposes into two simpler, well-known operations: transpose (flip across the diagonal), then reverse each row.

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

  // transpose: swap matrix[r][c] with matrix[c][r]
  for (let r = 0; r < n; r++) {
    for (let c = r + 1; c < n; c++) { // c starts at r+1 — never touch the diagonal or repeat a swap
      [matrix[r][c], matrix[c][r]] = [matrix[c][r], matrix[r][c]];
    }
  }

  // reverse each row
  for (const row of matrix) row.reverse();
}

Other rotations, flips, and non-square matrices

The clockwise recipe (transpose, then reverse each row) is one entry in a small family. Each of the other moves is a composition of the same two building blocks, and you can reconstruct any of them by tracking where the corner cell goes.

function rotateCounterclockwise(matrix) {
  const n = matrix.length;
  for (let r = 0; r < n; r++) {
    for (let c = r + 1; c < n; c++) {
      [matrix[r][c], matrix[c][r]] = [matrix[c][r], matrix[r][c]];
    }
  }
  matrix.reverse(); // reverse the row order in place; rows themselves are untouched
}

Two follow-ups come up. First, "do it in one pass". Each cell belongs to a cycle of four: the cell, the cell it moves to, where that one moves, and where the last one moves, which is the starting cell again. Rotate those four values together, layer by layer from the outside in.

function rotateByCycles(matrix) {
  const n = matrix.length;
  for (let r = 0; r < Math.floor(n / 2); r++) {
    for (let c = r; c < n - 1 - r; c++) {
      const tmp = matrix[r][c];
      matrix[r][c] = matrix[n - 1 - c][r];                       // left side moves to the top
      matrix[n - 1 - c][r] = matrix[n - 1 - r][n - 1 - c];       // bottom moves to the left side
      matrix[n - 1 - r][n - 1 - c] = matrix[c][n - 1 - r];       // right side moves to the bottom
      matrix[c][n - 1 - r] = tmp;                                // the saved top moves to the right side
    }
  }
}

The loop bounds are the part to rehearse. r runs over the first half of the layers. A layer's side has n - 2r cells, and the cycles start only at the first n - 2r - 1 of them (c stops before n - 1 - r), because the last cell of one side is the first cell of the next side and is already moved by a cycle that starts there. For an odd n the centre cell never moves. Both versions are O(n²) time and O(1) space.

Second, a non-square matrix cannot be rotated in place, because a rows × cols grid becomes cols × rows; you allocate the result. The index rule for clockwise is result[c][rows - 1 - r] = matrix[r][c], and a plain transpose is result[c][r] = matrix[r][c].

function rotateClockwiseCopy(matrix) {
  const rows = matrix.length, cols = matrix[0].length;
  const result = Array.from({ length: cols }, () => new Array(rows));
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) result[c][rows - 1 - r] = matrix[r][c];
  }
  return result;
}

function transpose(matrix) {
  return Array.from({ length: matrix[0].length }, (_, c) => matrix.map(row => row[c]));
}

rotateClockwiseCopy([[1, 2, 3], [4, 5, 6]]); // [[4, 1], [5, 2], [6, 3]]

A quick sanity check for any rotation code is to apply it four times and confirm the matrix returns to where it started.

Set Matrix Zeroes: the matrix stores its own markers

Whenever a cell is 0, zero its entire row and column. Zeroing as you scan is wrong, because the zeros you just wrote look like original zeros and wipe too much. The straightforward fix records the zero rows and columns in two extra arrays (O(rows + cols) space). The O(1)-space version stores those markers inside the matrix: use the first cell of each row as "this row must be zeroed" and the first cell of each column as "this column must be zeroed". That overwrites the first row and first column, so remember separately whether they held a zero themselves.

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

  for (let c = 0; c < cols; c++) if (matrix[0][c] === 0) firstRowZero = true;
  for (let r = 0; r < rows; r++) if (matrix[r][0] === 0) firstColZero = true;

  for (let r = 1; r < rows; r++) {          // pass 1: record zeros into the first row and column
    for (let c = 1; c < cols; c++) {
      if (matrix[r][c] === 0) { matrix[r][0] = 0; matrix[0][c] = 0; }
    }
  }
  for (let r = 1; r < rows; r++) {          // pass 2: apply them to the interior only
    for (let c = 1; c < cols; c++) {
      if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0;
    }
  }
  if (firstRowZero) for (let c = 0; c < cols; c++) matrix[0][c] = 0; // last: the markers are no longer needed
  if (firstColZero) for (let r = 0; r < rows; r++) matrix[r][0] = 0;
}

Dry run: [[1,1,1],[1,0,1],[1,1,1]]

Time O(rows · cols), extra space O(1). The ordering is where bugs live. Pass 2 must skip the first row and column, because applying a marker to the marker cells destroys information the other cells still need, and the two flags must be applied last, though they have to be computed first: computed after pass 1, they would read cells that pass 1 has already overwritten.

Game of Life: two states in one cell

Each cell is alive (1) or dead (0). A live cell survives with 2 or 3 live neighbours; a dead cell comes alive with exactly 3; everything else is dead next turn. All cells update simultaneously, so overwriting a cell while scanning corrupts the neighbour counts of later cells. Copying the board is O(rows · cols) extra space. To stay in place, let each cell hold both the old and the new state: bit 0 is the old state and bit 1 is the new state. Neighbour counts always read bit 0 (& 1), which writing bit 1 never disturbs.

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

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      let live = 0;
      for (let dr = -1; dr <= 1; dr++) {
        for (let dc = -1; dc <= 1; dc++) {
          if (dr === 0 && dc === 0) continue;
          const nr = r + dr, nc = c + dc;
          if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
            live += board[nr][nc] & 1; // the OLD state, even in cells already updated
          }
        }
      }
      const alive = board[r][c] & 1;
      const next = alive ? live === 2 || live === 3 : live === 3;
      if (next) board[r][c] |= 2; // write the new state into bit 1
    }
  }
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) board[r][c] >>= 1; // the new state becomes the only state
  }
}

Dry run: a vertical blinker, [[0,1,0],[0,1,0],[0,1,0]]

The board after the first scan is [[0,1,0],[2,3,2],[0,1,0]], and shifting every value right by one gives [[0,0,0],[1,1,1],[0,0,0]], the horizontal blinker. Time O(rows · cols · 8) = O(rows · cols), extra space O(1). Reading a neighbour as board[nr][nc] === 1 instead of & 1 is the classic bug: an already-updated neighbour holding 3 (alive before and after) is then missed, although it was alive. On a board that is infinite or mostly empty, the expected follow-up is to store only the live coordinates in a set and count neighbours by incrementing a map around each live cell.

Grid as a graph — search patterns from the graph chapter, reused

Any grid problem involving "connected region," "flood fill," or "shortest path between cells" is the graph-traversal chapters applied directly: each cell is a node, each of its up-to-4 orthogonal neighbors is an edge.

function numIslands(grid) {
  if (grid.length === 0) return 0;
  const rows = grid.length, cols = grid[0].length;
  let islands = 0;

  function sink(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== "1") return;
    grid[r][c] = "0"; // mark visited by mutating the grid — avoids a separate visited set
    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1") {
        islands++;
        sink(r, c); // flood-fill the whole island so it's never counted twice
      }
    }
  }
  return islands;
}

Searching a sorted matrix: three different shapes

"Sorted matrix" can mean three different things, and each one has its own search. Read which ordering the problem promises before choosing.

Shape 1: rows sorted, and each row starts higher than the previous row ends

Then reading row by row gives one sorted list of rows · cols numbers. Binary search it without building it, by converting the flat index mid back to (Math.floor(mid / cols), mid % cols).

function searchMatrix(matrix, target) {
  const rows = matrix.length, cols = matrix[0].length;
  let lo = 0, hi = rows * cols - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    const value = matrix[Math.floor(mid / cols)][mid % cols];
    if (value === target) return true;
    if (value < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return false;
}

O(log(rows · cols)) time, O(1) space.

Shape 2: every row sorted and every column sorted, nothing else

Now the rows are not chained, so flat binary search is wrong (the last value of one row can exceed the first of the next). Start at the top-right corner. That cell is the largest in its row and the smallest in its column, so one comparison discards a whole line. If the value is bigger than the target, everything below it in the column is bigger still, so move left. If it is smaller, everything to its left in the row is smaller still, so move down.

function searchMatrixII(matrix, target) {
  let r = 0, c = matrix[0].length - 1;
  while (r < matrix.length && c >= 0) {
    const value = matrix[r][c];
    if (value === target) return true;
    if (value > target) c--; // the rest of column c is larger than value
    else r++;                // the rest of row r, to the left, is smaller than value
  }
  return false;
}

The table traces the 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]]. Each step removes one row or one column, so the walk takes at most rows + cols steps: O(rows + cols) time, O(1) space. The top-left corner would not work, because both of its neighbours are larger and a comparison cannot say which way to go; only corners where one direction increases and the other decreases give a decision.

Shape 3: kth smallest in a row- and column-sorted matrix

The k-th smallest is not at a computable position, but you can binary search on the value. For a candidate x, count how many cells are <= x with the staircase walk from the bottom-left corner; the count rises with x. The answer is the smallest x whose count reaches k, and that x is always a value that is in the matrix (the count only jumps at a value that exists).

function countAtMost(matrix, limit) {
  const rows = matrix.length, cols = matrix[0].length;
  let count = 0, r = rows - 1, c = 0; // bottom-left: smallest in its row, largest in its column
  while (r >= 0 && c < cols) {
    if (matrix[r][c] <= limit) {
      count += r + 1; // this cell and everything above it in the column
      c++;
    } else {
      r--;
    }
  }
  return count;
}

function kthSmallest(matrix, k) {
  const rows = matrix.length, cols = matrix[0].length;
  let lo = matrix[0][0], hi = matrix[rows - 1][cols - 1];
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (countAtMost(matrix, mid) >= k) hi = mid; // mid could be the answer: keep it
    else lo = mid + 1;
  }
  return lo;
}

Dry run: [[1,5,9],[10,11,13],[12,13,15]], k = 8

The answer is 13. Each count is O(rows + cols) and the search takes O(log(max - min)) rounds, so O((rows + cols) · log(max - min)) time with O(1) space. The alternative is a min-heap holding the first element of each row, popping k times and pushing the popped cell's right neighbour: O(k log rows). Prefer the value search when k is large and the heap when k is small.

Valid Sudoku: row, column and box in one pass

The board is valid when no digit repeats in any row, column or 3 × 3 box (the board can be unsolvable and still be valid; only the digits already placed are checked). One pass over the 81 cells with a "seen" set per row, per column and per box does it. The only thing to derive is the box number of a cell: boxes are numbered 0 to 8 in row-major order, so the box row is Math.floor(r / 3), the box column is Math.floor(c / 3), and box = Math.floor(r / 3) * 3 + Math.floor(c / 3). For the cell at row 4, column 7 that gives 1 * 3 + 2 = 5, the middle-right box.

function isValidSudoku(board) {
  const rows = new Array(9).fill(0);
  const cols = new Array(9).fill(0);
  const boxes = new Array(9).fill(0); // each entry is a bitmask of digits seen: bit d-1 for digit d

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const ch = board[r][c];
      if (ch === ".") continue;
      const bit = 1 << (ch.charCodeAt(0) - 49); // "1" is char code 49
      const box = Math.floor(r / 3) * 3 + Math.floor(c / 3);
      if ((rows[r] & bit) || (cols[c] & bit) || (boxes[box] & bit)) return false;
      rows[r] |= bit;
      cols[c] |= bit;
      boxes[box] |= bit;
    }
  }
  return true;
}

This is O(81), a constant, and the bitmask turns each membership test into one AND. A Set per row, column and box (keyed by digit, or one Set of strings such as "r4:7", "c7:7", "b5:7") is the same algorithm and is easier to say aloud. The usual slips are an off-by-one in the character code, skipping the box check, and using r / 3 without the floor, which gives fractions that never match.

Recognizing it in an unseen problem

• "Spiral," "rotate," "transpose," "diagonal" → boundary/index bookkeeping, work out the pattern on paper first
• "Islands," "regions," "flood fill," "shortest path in a grid" → it's a graph problem wearing a grid costume
• In-place mutation requested → look for a decomposition into two or more simpler, already-known transformations (like rotate = transpose + reverse)
• Always double-check boundary conditions on non-square grids — single row/column inputs break naive boundary logic first
• "Do it in place with O(1) extra space" on a grid → store extra information in the cells themselves: markers in the first row and column (zeroes), or two states in different bits of one cell (Game of Life)
• A matrix sorted "by rows and by columns" → staircase from a corner (search, count); sorted as one flattened list → binary search on the flat index; kth element of a sorted matrix → binary search on the value, or a heap
• Cells on the same diagonal → the key r - c (same main-direction diagonal) or r + c (same anti-diagonal)
• A path that turns when blocked (spiral, snake, bouncing) → a direction table and an "is the next cell usable" test, not hand-written case analysis
• Every fresh grid you build with fill deserves a second look for the shared-row trap