// ─────────────────────────────────────────────────────────────────────────────
// MATRICES (2-D GRIDS)
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : grid[r][c] indexing, traversal orders, in-place transforms, grid-as-graph search.
// TELL   : "m x n grid", "rotate image", "spiral", "islands", "flood fill", "neighbors", "cells",
//          "minutes until all ...", "search a sorted matrix".
// SAY    : row-major, directions array, in-bounds check, transpose, reverse rows, multi-source BFS,
//          staircase search, sentinel / marker values, 4-directional vs 8-directional neighbors.
// BIG-O  : O(mn) for any full traversal; BFS/DFS on grid O(mn); staircase search O(m + n).
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── 1. Directions idiom + in-bounds helper  —  iterate neighbors with one loop
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]];
assert.deepEqual(neighbors(g3, 0, 0), [[1, 0], [0, 1]]);
assert.equal(neighbors(g3, 1, 1, DIRS8).length, 8);
assert.equal(inBounds(g3, 3, 0), false);

// ── 2. Traverse row-major / col-major  —  row-major is cache-friendly and matches memory layout
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; };
assert.deepEqual(rowMajor(g3), [1, 2, 3, 4, 5, 6, 7, 8, 9]);
assert.deepEqual(colMajor(g3), [1, 4, 7, 2, 5, 8, 3, 6, 9]);
// create m x n: Array.from({ length: m }, () => new Array(n).fill(0))   -- NEVER new Array(m).fill([]) (shared row!)

// ── 3. Transpose  —  out[c][r] = g[r][c]; works for non-square  —  O(mn)
const transpose = (g) => g[0].map((_, c) => g.map((row) => row[c]));
assert.deepEqual(transpose([[1, 2, 3], [4, 5, 6]]), [[1, 4], [2, 5], [3, 6]]);
assert.deepEqual(transpose([[1]]), [[1]]);

// ── 4. Rotate 90 clockwise in place  —  transpose then reverse each row. CCW: transpose then reverse each COLUMN (or reverse rows first)  —  O(n^2) / O(1)
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;
}
assert.deepEqual(rotateCW([[1, 2, 3], [4, 5, 6], [7, 8, 9]]), [[7, 4, 1], [8, 5, 2], [9, 6, 3]]);
assert.deepEqual(rotateCCW([[1, 2, 3], [4, 5, 6], [7, 8, 9]]), [[3, 6, 9], [2, 5, 8], [1, 4, 7]]);
assert.deepEqual(rotateCW([[1]]), [[1]]);

// ── 5. Spiral order  —  four shrinking boundaries top/bottom/left/right; check bounds before bottom row and left col  —  O(mn)
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;
}
assert.deepEqual(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]), [1, 2, 3, 6, 9, 8, 7, 4, 5]);
assert.deepEqual(spiralOrder([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]), [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]);
assert.deepEqual(spiralOrder([[1], [2], [3]]), [1, 2, 3]);

// ── 6. Set matrix zeroes, O(1) space  —  use row 0 / col 0 as the marker arrays; separate flag for col 0  —  O(mn) / O(1)
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;
}
assert.deepEqual(setZeroes([[1, 1, 1], [1, 0, 1], [1, 1, 1]]), [[1, 0, 1], [0, 0, 0], [1, 0, 1]]);
assert.deepEqual(setZeroes([[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]), [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]);
assert.deepEqual(setZeroes([[1]]), [[1]]);

// ── 7. Search 2D matrix I (fully sorted as flat)  —  binary search on index 0..mn-1  —  O(log mn)
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;
}
// ── 8. Search 2D matrix II (rows and cols sorted), staircase  —  start top-right; too big -> left, too small -> down  —  O(m + n)
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;
}
assert.equal(searchMatrixI([[1, 3, 5], [7, 9, 11]], 9), true);
assert.equal(searchMatrixI([[1, 3, 5], [7, 9, 11]], 4), false);
assert.equal(searchMatrixII([[1, 4, 7], [2, 5, 8], [3, 6, 9]], 5), true);
assert.equal(searchMatrixII([[1, 4, 7], [2, 5, 8], [3, 6, 9]], 10), false);

// ── 9. Number of islands (DFS)  —  sink visited land  —  O(mn)
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;
}
assert.equal(numIslands([['1', '1', '0', '0'], ['0', '1', '0', '1'], ['0', '0', '0', '1']]), 2);
assert.equal(numIslands([['0']]), 0);

// ── 10. Flood fill  —  DFS from (sr, sc) over cells equal to the original color; guard same-color no-op  —  O(mn)
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;
}
assert.deepEqual(floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2), [[2, 2, 2], [2, 2, 0], [2, 0, 1]]);
assert.deepEqual(floodFill([[0, 0], [0, 0]], 0, 0, 0), [[0, 0], [0, 0]]); // same color: no infinite loop

// ── 11. Max area of island  —  DFS returns 1 + sum of neighbors  —  O(mn)
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;
}
assert.equal(maxAreaOfIsland([[0, 1, 1, 0], [0, 1, 0, 0], [1, 0, 0, 1]]), 3);
assert.equal(maxAreaOfIsland([[0, 0]]), 0);

// ── 12. Rotting oranges (multi-source BFS)  —  enqueue ALL rotten first; BFS by levels; answer = levels; fail if fresh remains  —  O(mn)
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;
}
assert.equal(orangesRotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]), 4);
assert.equal(orangesRotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]), -1);
assert.equal(orangesRotting([[0, 2]]), 0);

// ── 13. Diagonal traversal (zigzag)  —  cells on the same anti-diagonal share r + c; alternate direction by parity  —  O(mn)
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;
}
assert.deepEqual(findDiagonalOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]), [1, 2, 4, 7, 5, 3, 6, 8, 9]);
assert.deepEqual(findDiagonalOrder([[1, 2], [3, 4]]), [1, 2, 3, 4]);

// ── 14. Game of life neighbor counting  —  8-dir count; encode next state in extra bits (bit 1) to stay in place  —  O(mn) / O(1)
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;
}
assert.deepEqual(gameOfLife([[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]]), [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]]);
assert.deepEqual(gameOfLife([[1, 1], [1, 0]]), [[1, 1], [1, 1]]);

// ── 15. Pascal's triangle  —  row[i][j] = row[i-1][j-1] + row[i-1][j]; edges are 1  —  O(n^2)
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;
}
assert.deepEqual(pascal(5), [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]);
assert.deepEqual(pascal(0), []);

// ── 16. Word search (grid DFS + backtrack)  —  mark '#', try 4 dirs, restore  —  O(mn * 3^L)
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']];
assert.equal(exist(wb, 'SEE'), true);
assert.equal(exist(wb, 'ABCB'), false);

console.log('ok: algorithms/matrices.js');