Matrix Problems

Traverse the matrix layer by layer from outside in. Maintain four boundaries: top, bottom, left, right. After each direction, shrink the corresponding boundary.

Four traversals per layer: right along top row, down along right column, left along bottom row, up along left column. Repeat until boundaries cross.

The boundary checks if (t <= b) and if (l <= r) before bottom-left and left-bottom traversals prevent double-printing in non-square matrices.

function spiralOrder(m) {
  const res = [], dirs = [];
  let t = 0, b = m.length-1, l = 0, r = m[0].length-1;
  while (t <= b && l <= r) {
    for (let i = l; i <= r; i++) res.push(m[t][i]); t++; // top row
    for (let i = t; i <= b; i++) res.push(m[i][r]); r--; // right col
    if (t <= b) { for (let i = r; i >= l; i--) res.push(m[b][i]); b--; } // bottom row
    if (l <= r) { for (let i = b; i >= t; i--) res.push(m[i][l]); l++; } // left col
  }
  return res;
}
// 3x3: [[1,2,3],[4,5,6],[7,8,9]] => [1,2,3,6,9,8,7,4,5]

Boundary shrinks after each side is traversed. The 4-direction order is: RIGHT, DOWN, LEFT, UP.

Works for any m×n matrix, not just square. The boundary checks prevent elements being double-counted in single-row or single-column matrices.

Transposing reflects the matrix over its main diagonal: element at (i,j) moves to (j,i). The rows become columns and columns become rows.

For an m×n matrix, the transpose is n×m. Square matrices can be transposed in-place; non-square requires a new matrix.

Transposing is a key step in many algorithms: matrix multiplication, solving linear systems, and the rotate-90° algorithm.

// Non-square matrix transpose: O(m*n)
function transpose(m) {
  return m[0].map((_, j) => m.map(row => row[j]));
}

// OR with explicit loops:
function transposeExplicit(m) {
  const rows = m.length, cols = m[0].length;
  const result = Array.from({length: cols}, () => Array(rows));
  for (let i = 0; i < rows; i++)
    for (let j = 0; j < cols; j++)
      result[j][i] = m[i][j];
  return result;
}
// [[1,2,3],[4,5,6]] => [[1,4],[2,5],[3,6]]

In-place (square only): swap m[i][j] and m[j][i] for j>i. Non-square requires a new array.

The map-based solution is elegant: for each column index j, create a new row by mapping all rows at that column.

Primary diagonal elements are at indices (i,i) where i goes 0 to n-1. Secondary (anti-) diagonal elements are at (i, n-1-i). Both can be summed in a single pass.

For odd-sized matrices, the center element (n/2, n/2) appears in BOTH diagonals — subtract it once to avoid double-counting.

This is a common matrix interview question. Time O(n), Space O(1).

function diagonalSum(m) {
  const n = m.length;
  let sum = 0;
  for (let i = 0; i < n; i++) {
    sum += m[i][i];          // primary diagonal
    sum += m[i][n - 1 - i]; // secondary diagonal
  }
  if (n % 2) sum -= m[Math.floor(n/2)][Math.floor(n/2)]; // center counted twice
  return sum;
}
// [[1,2,3],[4,5,6],[7,8,9]] => 1+5+9 + 3+5+7 - 5 = 25
// [[1,2],[3,4]]             => (1+4) + (2+3) = 10 (no center)

Subtract center once for odd n: the center is at (n//2, n//2) and sits on BOTH diagonals simultaneously.

n=4: no center element needing correction. n=3: center (1,1) used by both diagonals. n=5: center (2,2) used by both.

For a matrix where each row is sorted left-to-right and each column sorted top-to-bottom, start from the TOP-RIGHT corner. This position has a unique property: it's the maximum of its row and minimum of its column.

If target < current: move LEFT (current is too big for this row). If target > current: move DOWN (current is too small for this column). Each comparison eliminates one row or column.

Time O(m+n) — much better than O(mn) brute force or O(mn log(mn)) with sorting.

function searchMatrix(m, target) {
  let r = 0, c = m[0].length - 1; // start top-right
  while (r < m.length && c >= 0) {
    if (m[r][c] === target) return [r, c]; // found
    if (m[r][c] > target) c--;  // too big, go left
    else r++;                    // too small, go down
  }
  return null; // not found
}
// [[1,4,7],[2,5,8],[3,6,9]], target=5 => [1,1]
// [[1,4,7],[2,5,8],[3,6,9]], target=10 => null

Top-right corner is key: it's max of row (can eliminate row when too small) and min of column (can eliminate col when too big).

Starting from top-left wouldn't work: if target > m[0][0], we don't know whether to go right or down.

Two-pass approach with O(m+n) extra space: first scan the matrix recording which rows and columns contain zeros. Second pass sets those rows and columns to zero.

Don't set zeros during the first pass! Setting zeros would corrupt the matrix and cause false positives in subsequent scans.

The O(1) space version uses the first row and column as markers (shown separately). This Set-based version is clearer to understand.

function zeroMatrix(m) {
  const zeroRows = new Set(), zeroCols = new Set();
  // Pass 1: find which rows and cols have zeros
  for (let i = 0; i < m.length; i++)
    for (let j = 0; j < m[0].length; j++)
      if (m[i][j] === 0) { zeroRows.add(i); zeroCols.add(j); }
  // Pass 2: zero out the flagged rows and columns
  for (let i = 0; i < m.length; i++)
    for (let j = 0; j < m[0].length; j++)
      if (zeroRows.has(i) || zeroCols.has(j)) m[i][j] = 0;
  return m;
}
// [[1,1,1],[1,0,1],[1,1,1]] => [[1,0,1],[0,0,0],[1,0,1]]

Two separate passes are required: if we zero during scan, we create false positives in rows/columns that originally had no zeros.

Space: O(m+n) for the Sets. For O(1) space, use the matrix's first row and column as flag arrays.

Boundary elements form the outer ring: first row, last column, last row (reversed), first column (reversed). For a 1x1 matrix, just the single element. For 1-row or 1-col, handle carefully to avoid double-printing.

Traverse: right along row 0, down along last column (skip row 0), left along last row (skip last col), up along first column (skip first and last rows).

This is similar to the spiral order first layer — same four directions, print once.

function boundaryTraversal(m) {
  const res = [], rows = m.length, cols = m[0].length;
  for (let j = 0; j < cols; j++) res.push(m[0][j]);            // top row
  for (let i = 1; i < rows; i++) res.push(m[i][cols - 1]);    // right col
  if (rows > 1) for (let j = cols-2; j >= 0; j--) res.push(m[rows-1][j]); // bottom row
  if (cols > 1) for (let i = rows-2; i > 0; i--) res.push(m[i][0]);       // left col
  return res;
}
// [[1,2,3],[4,5,6],[7,8,9]] => [1,2,3,6,9,8,7,4]

Guards on rows and cols prevent double-printing corners in 1-row or 1-column matrices.

For a 3×3 matrix: top(1,2,3) + right(6,9) + bottom(8,7) + left(4) = outer 8 elements.

A saddle point is an element that is the minimum in its row AND the maximum in its column. Named after the saddle shape which has a minimum in one direction and maximum in the other.

For each row, find the minimum value and its column position. Then check if that column-position element is the max of its column.

Saddle points don't always exist. When they do, they represent equilibrium points in game theory (minimax theorem).

function saddlePoint(m) {
  for (let i = 0; i < m.length; i++) {
    const minVal = Math.min(...m[i]);        // row minimum
    const j = m[i].indexOf(minVal);          // column of row-min
    const colMax = Math.max(...m.map(r => r[j])); // max of that column
    if (minVal === colMax) return { row: i, col: j, value: minVal };
  }
  return null; // no saddle point
}
// [[3,4,2],[1,5,3],[4,2,0]] => saddle at (2,2) value=0? Let's verify...
// [[3,1,6],[2,5,4]] => row0 min=1(col1), col1 max=max(1,5)=5≠1 => no saddle

A matrix can have at most one saddle point (if it exists in a matrix with distinct elements).

In game theory, saddle points represent optimal strategies in zero-sum games where no player benefits from changing strategy.

Matrix multiplication C = A × B requires A to be m×k and B to be k×n. Result C is m×n. Element C[i][j] = dot product of row i of A with column j of B.

Three nested loops: outer two iterate result position (i,j), inner loop k computes the dot product by summing products of A[i][k] * B[k][j].

Standard algorithm is O(m*k*n). Strassen's algorithm reduces to O(n^2.81) — practical for very large matrices.

function multiply(a, b) {
  const m = a.length, k = a[0].length, n = b[0].length;
  const res = Array.from({length: m}, () => Array(n).fill(0));
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      for (let p = 0; p < k; p++)
        res[i][j] += a[i][p] * b[p][j];
  return res;
}
// [[1,2],[3,4]] x [[5,6],[7,8]] => [[19,22],[43,50]]

Prerequisite: number of columns in A must equal number of rows in B. Result dimensions: (rows of A) × (cols of B).

Matrix multiplication is NOT commutative: A×B ≠ B×A in general. But it IS associative: (A×B)×C = A×(B×C).

The challenge is zeroing rows/columns without using O(m+n) extra space to track which rows/columns contain zeros.

Solution: use the first row and first column as markers. Scan the matrix and mark zero positions in the first row/column. Then apply zeros based on those markers.

Track separately whether the first row and first column themselves need to be zeroed — because they serve a dual purpose as markers.

function setZeroes(m) {
  let firstRow = false, firstCol = false;
  for (let i = 0; i < m.length; i++)
    for (let j = 0; j < m[0].length; j++)
      if (m[i][j] === 0) {
        if (i === 0) firstRow = true;
        if (j === 0) firstCol = true;
        m[i][0] = 0; m[0][j] = 0;
      }
  for (let i = 1; i < m.length; i++)
    for (let j = 1; j < m[0].length; j++)
      if (m[i][0] === 0 || m[0][j] === 0) m[i][j] = 0;
  if (firstRow) m[0].fill(0);
  if (firstCol) for (let i = 0; i < m.length; i++) m[i][0] = 0;
}

Two-pass approach: first pass marks, second pass zeroes. O(1) extra space (only two booleans).

The order matters: apply the body zeroes (using markers) BEFORE zeroing the first row/column (the markers themselves).

In-place 90° clockwise rotation: first transpose the matrix (swap m[i][j] with m[j][i]), then reverse each row.

Transposing flips the matrix along its main diagonal. Reversing each row then converts a counter-clockwise rotation into clockwise.

This is O(n²) time and O(1) space — no extra matrix needed.

function rotate90(m) {
  const n = m.length;
  // Step 1: Transpose (swap i,j with j,i)
  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]];
  // Step 2: Reverse each row
  m.forEach(row => row.reverse());
  return m;
}
// [[1,2,3],[4,5,6],[7,8,9]] => [[7,4,1],[8,5,2],[9,6,3]]

Anti-clockwise rotation: reverse each row first, THEN transpose (swap steps).

180° rotation: either apply 90° twice, or reverse entire matrix then reverse each row.

Use four boundary variables (top, bottom, left, right) that shrink as each layer is traversed: right along top, down along right, left along bottom, up along left.

After each direction, shrink the corresponding boundary. Check that boundaries haven't crossed before each traversal direction to handle non-square matrices.

This peels off one "ring" of the matrix at a time, working inward.

function spiralOrder(m) {
  const res = [];
  let t = 0, b = m.length - 1, l = 0, r = m[0].length - 1;
  while (t <= b && l <= r) {
    for (let i = l; i <= r; i++) res.push(m[t][i]); t++;
    for (let i = t; i <= b; i++) res.push(m[i][r]); r--;
    if (t <= b) { for (let i = r; i >= l; i--) res.push(m[b][i]); b--; }
    if (l <= r) { for (let i = b; i >= t; i--) res.push(m[i][l]); l++; }
  }
  return res;
}
// [[1,2,3],[4,5,6],[7,8,9]] => [1,2,3,6,9,8,7,4,5]

Boundary checks after top++ and right-- prevent double-printing middle row/column in non-square matrices.

This pattern generalizes to any m×n matrix, not just square ones.

An island is a group of connected 1s (horizontally and vertically adjacent). Use DFS/BFS: when a '1' is found, increment count and flood-fill all connected 1s to 0 (to mark as visited).

This is a classic graph connectivity problem on a grid — same pattern as connected components in an undirected graph.

Time O(m*n) — each cell is visited at most once. Space O(m*n) in worst case for the recursion stack.

function numIslands(grid) {
  if (!grid.length) return 0;
  let count = 0;
  function dfs(i, j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return;
    if (grid[i][j] !== '1') return;
    grid[i][j] = '0'; // mark visited
    dfs(i+1,j); dfs(i-1,j); dfs(i,j+1); dfs(i,j-1);
  }
  for (let i = 0; i < grid.length; i++)
    for (let j = 0; j < grid[0].length; j++)
      if (grid[i][j] === '1') { count++; dfs(i, j); }
  return count;
}
// [["1","1","0"],["0","1","0"],["0","0","1"]] => 2

Flood-fill marks visited cells by changing '1' to '0' — no extra visited array needed.

For immutable input, use a separate visited boolean array or Union-Find instead of modifying the grid.

In a matrix where you can only move RIGHT or DOWN, there are exactly C(m+n-2, m-1) unique paths. Enumerate them using DFS/backtracking.

At each cell, try going right (if possible) and going down (if possible). When reaching (m-1, n-1), add the current path to results.

Path count grows exponentially — for large matrices, just count paths (DP) rather than enumerate them.

function allPaths(grid) {
  const m = grid.length, n = grid[0].length, paths = [];
  function dfs(i, j, path) {
    if (i === m-1 && j === n-1) { paths.push([...path, grid[i][j]]); return; }
    path.push(grid[i][j]);
    if (i + 1 < m) dfs(i+1, j, path);
    if (j + 1 < n) dfs(i, j+1, path);
    path.pop(); // backtrack
  }
  dfs(0, 0, []);
  return paths;
}
// 2x2 grid: paths from (0,0) to (1,1) — 2 paths
// 3x3 grid: 6 paths (C(4,2)=6)

Backtrack after each recursion (path.pop()) to restore state — classic backtracking pattern.

For just counting paths (not enumerating): DP with dp[i][j] = dp[i-1][j] + dp[i][j-1]. O(n²) time, O(1) space.

At each cell, you can move right or down. Use DP: dp[i][j] = max sum to reach (i,j) = grid[i][j] + max(dp[i-1][j], dp[i][j-1]).

Fill the first row (can only come from left) and first column (can only come from above) as base cases, then fill remaining cells.

This is the classic path DP problem — foundation for many interview questions about grid navigation.

function maxSumPath(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({length: m}, (_, i) =>
    Array.from({length: n}, (_, j) => grid[i][j]));
  for (let i = 1; i < m; i++) dp[i][0] += dp[i-1][0];
  for (let j = 1; j < n; j++) dp[0][j] += dp[0][j-1];
  for (let i = 1; i < m; i++)
    for (let j = 1; j < n; j++)
      dp[i][j] += Math.max(dp[i-1][j], dp[i][j-1]);
  return dp[m-1][n-1];
}
// [[1,3,1],[1,5,1],[4,2,1]] => 12 (path 1→3→5→1→1)

DP recurrence: dp[i][j] = grid[i][j] + max(coming from above, coming from left).

Reconstruct the actual path by tracing back from dp[m-1][n-1] — at each step go to whichever neighbor had the larger dp value.

A row-sorted matrix where each row's first element is greater than the previous row's last can be treated as a 1D sorted array. Use binary search by mapping 1D index to 2D coordinates.

Map mid = (left+right)/2 to row = mid/n and col = mid%n where n is the number of columns.

This gives true O(log(m*n)) binary search on a matrix.

function searchMatrix(matrix, target) {
  if (!matrix.length) return false;
  const m = matrix.length, n = matrix[0].length;
  let left = 0, right = m * n - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const val = matrix[Math.floor(mid / n)][mid % n];
    if (val === target) return true;
    if (val < target) left = mid + 1;
    else right = mid - 1;
  }
  return false;
}
// matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target=3 => true

Key mapping: row = Math.floor(mid/n), col = mid%n converts 1D binary search index to 2D matrix position.

This only works for matrices where rows are individually sorted AND the first element of each row > last element of previous row.

In a weighted grid where each cell has a cost, find the path from top-left to bottom-right with minimum total cost. Moving right or down only.

DP: dp[i][j] = minimum cost to reach cell (i,j) = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

This is "Minimum Path Sum" (LeetCode 64) — the cost variant of the max-sum/count-paths grid problems.

function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) continue;
      const fromTop  = i > 0 ? grid[i-1][j] : Infinity;
      const fromLeft = j > 0 ? grid[i][j-1] : Infinity;
      grid[i][j] += Math.min(fromTop, fromLeft);
    }
  return grid[m-1][n-1];
}
// [[1,3,1],[1,5,1],[4,2,1]] => 7 (1+3+1+1+1)

Modifies grid in-place to save space. Copy the grid first if original must be preserved.

For graphs with arbitrary movement (not just right/down), use Dijkstra's algorithm with a priority queue instead.

Standard unique paths DP, modified: if a cell contains an obstacle (1), set dp[i][j] = 0 (can't reach that cell). Otherwise use the normal recurrence.

Base case: if start or end has an obstacle, return 0 immediately.

This is the "Unique Paths II" problem — same DP as before but with blocked cells.

function uniquePathsWithObstacles(grid) {
  const m = grid.length, n = grid[0].length;
  if (grid[0][0] === 1 || grid[m-1][n-1] === 1) return 0;
  const dp = Array.from({length: m}, () => Array(n).fill(0));
  dp[0][0] = 1;
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) continue;
      if (grid[i][j] === 1) { dp[i][j] = 0; continue; }
      dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);
    }
  return dp[m-1][n-1];
}
// [[0,0,0],[0,1,0],[0,0,0]] => 2 (obstacle blocks one path)

Obstacle = dp value 0 naturally blocks paths through that cell from contributing to subsequent calculations.

Space can be optimized to O(n) using a 1D DP array since each row only depends on the previous row.

Row-major order: elements are read left-to-right, top-to-bottom. Flattening converts a 2D array to a 1D array following this order.

In JavaScript, Array.flat() handles this in one line. For arbitrary depth nesting, use Infinity as the argument.

The element at position (i, j) in an m×n matrix maps to 1D index i*n + j — useful for implementing 2D arrays in languages without native 2D support.

// Modern approach:
function flattenMatrix(matrix) {
  return matrix.flat();
}

// Manual approach (row-major):
function flattenManual(matrix) {
  const result = [];
  for (const row of matrix)
    for (const val of row)
      result.push(val);
  return result;
}
// [[1,2,3],[4,5,6],[7,8,9]] => [1,2,3,4,5,6,7,8,9]

// 1D index to 2D: row = Math.floor(idx/n), col = idx % n
// 2D to 1D: idx = row * n + col

Row-major order (C/JS) vs column-major order (Fortran/MATLAB) differ in which dimension varies fastest.

The 2D-to-1D index formula i*n+j is essential knowledge for implementing matrix operations efficiently in typed arrays.

DFS with memoization: from each cell, try all 4 directions and take the longest path. Cache results to avoid recomputing.

Since we can only move to strictly increasing cells, there are no cycles — the graph is a DAG, so memoization is valid.

Time O(m*n) with memoization — each cell computed exactly once. Without memoization: O(4^(m*n)) in worst case.

function longestIncreasingPath(matrix) {
  const m = matrix.length, n = matrix[0].length;
  const memo = Array.from({length: m}, () => Array(n).fill(0));
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  function dfs(i, j) {
    if (memo[i][j]) return memo[i][j];
    memo[i][j] = 1;
    for (const [di, dj] of dirs) {
      const ni = i + di, nj = j + dj;
      if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] > matrix[i][j])
        memo[i][j] = Math.max(memo[i][j], 1 + dfs(ni, nj));
    }
    return memo[i][j];
  }
  let max = 0;
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      max = Math.max(max, dfs(i, j));
  return max;
}
// [[9,9,4],[6,6,8],[2,1,1]] => 4 (path 1,2,6,9)

Check matrix[ni][nj] > matrix[i][j] (strictly greater) ensures we only move to larger values — prevents cycles.

Memoization gives huge speedup: without it, paths from high-value cells would be recomputed for every starting point.

A matrix is symmetric if it equals its own transpose: m[i][j] === m[j][i] for all i, j. Only square matrices can be symmetric.

Check only the upper triangle (i < j) against the lower triangle — no need to check the diagonal (always equal to itself) or both sides.

Symmetric matrices arise in many applications: adjacency matrices of undirected graphs, covariance matrices in statistics.

function isSymmetric(m) {
  const n = m.length;
  if (m.some(row => row.length !== n)) return false; // must be square
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j < n; j++)
      if (m[i][j] !== m[j][i]) return false;
  return true;
}
// [[1,2,3],[2,5,4],[3,4,7]] => true
// [[1,2,3],[2,5,4],[3,5,7]] => false (m[1][2]=4, m[2][1]=5)

Only check j > i — the upper triangle. Checking j < i would be redundant (testing swapped pairs already checked).

An undirected graph with n vertices has a symmetric adjacency matrix — each edge (u,v) appears in both m[u][v] and m[v][u].

Pascal's triangle in matrix form: row i contains Binomial coefficients C(i,0), C(i,1), ..., C(i,i). Each interior element is the sum of the two elements above it.

Generate iteratively: row 0 is [1], each subsequent row starts and ends with 1, and interior elements sum from the row above.

Pascal's triangle contains many patterns: row sums are powers of 2, Fibonacci appears diagonally, Sierpinski triangle emerges from odd numbers.

function generatePascal(numRows) {
  const triangle = [];
  for (let i = 0; i < numRows; i++) {
    const row = [1];
    const prev = triangle[i - 1] || [];
    for (let j = 1; j < i; j++) row.push(prev[j-1] + prev[j]);
    if (i > 0) row.push(1);
    triangle.push(row);
  }
  return triangle;
}
// generatePascal(5) =>
// [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Access any element: triangle[row][col] = C(row, col) = row! / (col! * (row-col)!).

Row 0 has 1 element, row 1 has 2, row n has n+1. Total elements in first n rows: n*(n+1)/2.

For row maxima: iterate each row and use Math.max with spread. For column maxima: transpose then do row maxima, or use a reduce over all rows for each column index.

Finding both row and column maxima is useful in saddle point detection and game theory matrix problems.

Time O(m*n) for both operations — each cell is visited once or twice.

function rowAndColMaxima(matrix) {
  const rowMax = matrix.map(row => Math.max(...row));
  const n = matrix[0].length;
  const colMax = Array.from({length: n}, (_, j) =>
    Math.max(...matrix.map(row => row[j]))
  );
  return { rowMax, colMax };
}
// [[1,5,2],[3,4,6],[7,2,1]] =>
// rowMax: [5,6,7]
// colMax: [7,5,6]

Math.max(...row) spreads the array as arguments. For very large rows (>100k elements), use reduce to avoid stack overflow from excessive arguments.

A saddle point is where an element is both the row minimum AND column maximum — exists at their intersection.

A sparse matrix has mostly zero entries. Storing it as a full 2D array wastes memory. Use a dictionary/map storing only non-zero entries as {row,col: value} pairs.

For matrix-vector multiplication with a sparse matrix, only iterate the non-zero entries — dramatically faster than iterating all m*n cells.

Real-world sparse matrices appear in graph adjacency, finite element methods, and machine learning (bag-of-words, recommendation systems).

class SparseMatrix {
  constructor(rows, cols) {
    this.rows = rows; this.cols = cols;
    this.data = new Map(); // key: "r,c" => value
  }
  set(r, c, val) {
    if (val !== 0) this.data.set(`${r},${c}`, val);
    else this.data.delete(`${r},${c}`); // remove zeros
  }
  get(r, c) { return this.data.get(`${r},${c}`) || 0; }
  
  // Multiply by dense vector
  multiply(vec) {
    const result = Array(this.rows).fill(0);
    for (const [key, val] of this.data) {
      const [r, c] = key.split(',').map(Number);
      result[r] += val * vec[c];
    }
    return result;
  }
}
// 1000x1000 matrix with 100 non-zeros: O(100) multiply vs O(10^6)

Sparse representation saves memory: O(nnz) space where nnz is number of non-zero elements, vs O(m*n) for dense.

CSR (Compressed Sparse Row) format is even more efficient for sequential row access, used in NumPy/SciPy.