Matrices (2-D Grids)

const DIRS4 = [[1, 0], [-1, 0], [0, 1], [0, -1]];const DIRS8 = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]];const inBounds = (g, r, c) => r >= 0 && c >= 0 && r < g.length && c < g[0].length;const neighbors = (g, r, c, dirs = DIRS4) => dirs.map(([dr, dc]) => [r + dr, c + dc]).filter(([nr, nc]) => inBounds(g, nr, nc));const g3 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];

const rowMajor = (g) => g.flat();const colMajor = (g) => { const out = []; for (let c = 0; c < g[0].length; c++) for (let r = 0; r < g.length; r++) out.push(g[r][c]); return out; };// create m x n: Array.from({ length: m }, () => new Array(n).fill(0))   -- NEVER new Array(m).fill([]) (shared row!)

const transpose = (g) => g[0].map((_, c) => g.map((row) => row[c]));

function rotateCW(m) {  const n = m.length;  for (let r = 0; r < n; r++) for (let c = r + 1; c < n; c++) [m[r][c], m[c][r]] = [m[c][r], m[r][c]]; // transpose  for (const row of m) row.reverse();  return m;}function rotateCCW(m) {  for (const row of m) row.reverse(); // reverse rows first ...  const n = m.length;  for (let r = 0; r < n; r++) for (let c = r + 1; c < n; c++) [m[r][c], m[c][r]] = [m[c][r], m[r][c]]; // ... then transpose  return m;}

function spiralOrder(m) {  const out = [];  if (m.length === 0) return out;  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++) out.push(m[top][c]);    top++;    for (let r = top; r <= bottom; r++) out.push(m[r][right]);    right--;    if (top <= bottom) { for (let c = right; c >= left; c--) out.push(m[bottom][c]); bottom--; }    if (left <= right) { for (let r = bottom; r >= top; r--) out.push(m[r][left]); left++; }  }  return out;}

function setZeroes(m) {  const R = m.length, C = m[0].length;  let col0 = false;  for (let r = 0; r < R; r++) {    if (m[r][0] === 0) col0 = true;    for (let c = 1; c < C; c++) if (m[r][c] === 0) { m[r][0] = 0; m[0][c] = 0; }  }  for (let r = R - 1; r >= 0; r--) { // bottom-up so markers in row 0 survive until used    for (let c = C - 1; c >= 1; c--) if (m[r][0] === 0 || m[0][c] === 0) m[r][c] = 0;    if (col0) m[r][0] = 0;  }  return m;}

function searchMatrixI(m, t) {  const R = m.length, C = m[0].length;  let lo = 0, hi = R * C - 1;  while (lo <= hi) {    const mid = (lo + hi) >> 1, v = m[(mid / C) | 0][mid % C];    if (v === t) return true;    if (v < t) lo = mid + 1; else hi = mid - 1;  }  return false;}

function searchMatrixII(m, t) {  let r = 0, c = m[0].length - 1;  while (r < m.length && c >= 0) {    if (m[r][c] === t) return true;    if (m[r][c] > t) c--; else r++;  }  return false;}

function numIslands(grid) {  let count = 0;  const sink = (r, c) => {    if (!inBounds(grid, r, c) || grid[r][c] !== '1') return;    grid[r][c] = '0';    for (const [dr, dc] of DIRS4) sink(r + dr, c + dc);  };  for (let r = 0; r < grid.length; r++) for (let c = 0; c < grid[0].length; c++) if (grid[r][c] === '1') { count++; sink(r, c); }  return count;}

function floodFill(img, sr, sc, color) {  const orig = img[sr][sc];  if (orig === color) return img;  const fill = (r, c) => {    if (!inBounds(img, r, c) || img[r][c] !== orig) return;    img[r][c] = color;    for (const [dr, dc] of DIRS4) fill(r + dr, c + dc);  };  fill(sr, sc);  return img;}

function maxAreaOfIsland(grid) {  const area = (r, c) => {    if (!inBounds(grid, r, c) || grid[r][c] !== 1) return 0;    grid[r][c] = 0;    return 1 + DIRS4.reduce((s, [dr, dc]) => s + area(r + dr, c + dc), 0);  };  let best = 0;  for (let r = 0; r < grid.length; r++) for (let c = 0; c < grid[0].length; c++) best = Math.max(best, area(r, c));  return best;}

function orangesRotting(grid) {  const q = [];  let fresh = 0;  for (let r = 0; r < grid.length; r++) for (let c = 0; c < grid[0].length; c++) {    if (grid[r][c] === 2) q.push([r, c]);    else if (grid[r][c] === 1) fresh++;  }  let minutes = 0;  for (let h = 0; h < q.length && fresh > 0; minutes++) {    const levelEnd = q.length; // process one level    for (; h < levelEnd; h++) {      const [r, c] = q[h];      for (const [dr, dc] of DIRS4) {        const nr = r + dr, nc = c + dc;        if (inBounds(grid, nr, nc) && grid[nr][nc] === 1) { grid[nr][nc] = 2; fresh--; q.push([nr, nc]); }      }    }  }  return fresh === 0 ? minutes : -1;}

function findDiagonalOrder(m) {  const R = m.length, C = m[0].length, out = [];  for (let d = 0; d < R + C - 1; d++) {    const cells = [];    for (let r = Math.max(0, d - C + 1); r <= Math.min(R - 1, d); r++) cells.push(m[r][d - r]);    out.push(...(d % 2 === 0 ? cells.reverse() : cells)); // even diagonals go up-right  }  return out;}

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 (const [dr, dc] of DIRS8) if (inBounds(b, r + dr, c + dc) && (b[r + dr][c + dc] & 1)) live++;    if ((b[r][c] & 1) && (live === 2 || live === 3)) b[r][c] |= 2; // survives    if (!(b[r][c] & 1) && live === 3) b[r][c] |= 2; // born  }  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) b[r][c] >>= 1; // shift next state into place  return b;}

function pascal(numRows) {  const out = [];  for (let i = 0; i < numRows; i++) {    const row = new Array(i + 1).fill(1);    for (let j = 1; j < i; j++) row[j] = out[i - 1][j - 1] + out[i - 1][j];    out.push(row);  }  return out;}

function exist(board, word) {  const dfs = (r, c, i) => {    if (i === word.length) return true;    if (!inBounds(board, r, c) || board[r][c] !== word[i]) return false;    const ch = board[r][c];    board[r][c] = '#';    const ok = DIRS4.some(([dr, dc]) => dfs(r + dr, c + dc, i + 1));    board[r][c] = ch;    return ok;  };  for (let r = 0; r < board.length; r++) for (let c = 0; c < board[0].length; c++) if (dfs(r, c, 0)) return true;  return false;}const wb = [['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']];