Grids and Matrices

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32const grid = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];
const rows = grid.length, cols = grid[0].length;
const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];

const inBounds = (r, c) => r >= 0 && r < rows && c >= 0 && c < cols;

function neighbours(r, c) {
  const found = [];
  for (const [dr, dc] of DIRS) {
    const nr = r + dr, nc = c + dc;
    if (inBounds(nr, nc)) found.push(grid[nr][nc]);
  }
  return found;
}

console.log('centre (1,1):', neighbours(1, 1));    // all four
console.log('corner (0,0):', neighbours(0, 0));    // only two
console.log('edge   (0,1):', neighbours(0, 1));    // three

// JavaScript does not throw on out-of-range row access, it gives undefined —
// and THEN indexing that throws. So the order of the check matters.
console.log('grid[5]      ->', grid[5]);
try {
  console.log(grid[5][0]);
} catch (err) {
  console.log('grid[5][0]   ->', err.constructor.name + ':', err.message);
}
console.log('grid[0][9]   ->', grid[0][9], '(no throw, just undefined — a silent bug)');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57function numIslandsDFS(inputGrid) {
  // Copy so the caller's grid is untouched, then sink land as we visit it.
  const g = inputGrid.map(row => [...row]);
  const rows = g.length, cols = g[0].length;
  let islands = 0;

  function sink(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (g[r][c] !== '1') return;             // water, or already sunk
    g[r][c] = '0';                            // mark visited BEFORE recursing
    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 (g[r][c] === '1') { islands++; sink(r, c); }

  return islands;
}

function numIslandsBFS(inputGrid) {
  const g = inputGrid.map(row => [...row]);
  const rows = g.length, cols = g[0].length;
  const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  let islands = 0;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (g[r][c] !== '1') continue;
      islands++;
      const queue = [[r, c]];
      g[r][c] = '0';                          // mark on ENQUEUE, not on dequeue
      for (let head = 0; head < queue.length; head++) {
        const [cr, cc] = queue[head];
        for (const [dr, dc] of DIRS) {
          const nr = cr + dr, nc = cc + dc;
          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
          if (g[nr][nc] !== '1') continue;
          g[nr][nc] = '0';
          queue.push([nr, nc]);
        }
      }
    }
  }
  return islands;
}

const map = [
  ['1', '1', '0', '0', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '1', '0', '0'],
  ['0', '0', '0', '1', '1'],
];
console.log('DFS:', numIslandsDFS(map), '| BFS:', numIslandsBFS(map));   // 3 each
console.log('all water:', numIslandsDFS([['0', '0'], ['0', '0']]));      // 0
console.log('all land: ', numIslandsDFS([['1', '1'], ['1', '1']]));      // 1
console.log('input unchanged:', map[0].join(''));                        // still 11000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53function maxAreaOfIsland(inputGrid) {
  const g = inputGrid.map(r => [...r]);
  const rows = g.length, cols = g[0].length;

  function measure(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || g[r][c] !== 1) return 0;
    g[r][c] = 0;
    return 1 + measure(r + 1, c) + measure(r - 1, c) + measure(r, c + 1) + measure(r, c - 1);
  }

  let best = 0;
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (g[r][c] === 1) best = Math.max(best, measure(r, c));
  return best;
}

// Distinct shapes: record each cell's offset from the island's first cell.
function numDistinctIslands(inputGrid) {
  const g = inputGrid.map(r => [...r]);
  const rows = g.length, cols = g[0].length;
  const shapes = new Set();

  function trace(r, c, baseR, baseC, path) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || g[r][c] !== 1) return;
    g[r][c] = 0;
    path.push(`${r - baseR},${c - baseC}`);        // relative coordinates
    trace(r + 1, c, baseR, baseC, path);
    trace(r - 1, c, baseR, baseC, path);
    trace(r, c + 1, baseR, baseC, path);
    trace(r, c - 1, baseR, baseC, path);
  }

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (g[r][c] === 1) {
        const path = [];
        trace(r, c, r, c, path);
        shapes.add(path.join('|'));
      }
  return shapes.size;
}

console.log('max area:', maxAreaOfIsland([
  [1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1],
]));   // 5 — the lone 1 on row 1 joins the bottom-right block

console.log('distinct shapes:', numDistinctIslands([
  [1, 1, 0, 1, 1],
  [1, 0, 0, 0, 0],
  [0, 0, 0, 1, 1],
  [0, 1, 0, 1, 0],
]));   // 3 — the two L-shapes are the same shape

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28function shortestPath(maze) {
  const rows = maze.length, cols = maze[0].length;
  if (maze[0][0] === 1 || maze[rows - 1][cols - 1] === 1) return -1;

  const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1));
  const queue = [[0, 0]];
  dist[0][0] = 0;

  for (let head = 0; head < queue.length; head++) {
    const [r, c] = queue[head];
    if (r === rows - 1 && c === cols - 1) return dist[r][c];

    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (maze[nr][nc] === 1 || dist[nr][nc] !== -1) continue;
      dist[nr][nc] = dist[r][c] + 1;
      queue.push([nr, nc]);
    }
  }
  return -1;                                   // the exit is unreachable
}

console.log('open 3x3:', shortestPath([[0, 0, 0], [0, 0, 0], [0, 0, 0]]));       // 4
console.log('with wall:', shortestPath([[0, 1, 0], [0, 1, 0], [0, 0, 0]]));      // 4
console.log('blocked:  ', shortestPath([[0, 1], [1, 0]]));                       // -1
console.log('single:   ', shortestPath([[0]]));                                  // 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38// Every rotten orange spreads to its fresh neighbours each minute, all at once.
function orangesRotting(inputGrid) {
  const g = inputGrid.map(r => [...r]);
  const rows = g.length, cols = g[0].length;
  const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  const queue = [];
  let fresh = 0;
  // Seed the queue with EVERY rotten orange. That is the whole trick.
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++) {
      if (g[r][c] === 2) queue.push([r, c]);
      else if (g[r][c] === 1) fresh++;
    }

  let minutes = 0, head = 0;
  while (head < queue.length && fresh > 0) {
    const levelSize = queue.length - head;      // process one minute at a time
    minutes++;
    for (let i = 0; i < levelSize; i++) {
      const [r, c] = queue[head++];
      for (const [dr, dc] of DIRS) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
        if (g[nr][nc] !== 1) continue;
        g[nr][nc] = 2;
        fresh--;
        queue.push([nr, nc]);
      }
    }
  }
  return fresh === 0 ? minutes : -1;            // some orange was unreachable
}

console.log(orangesRotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]));    // 4
console.log(orangesRotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]));    // -1, one is cut off
console.log(orangesRotting([[0, 2]]));                             // 0, nothing fresh
console.log(orangesRotting([[1]]));                                // -1, no source

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36// Count cells that CANNOT walk off the edge. Searching from every interior cell
// is wasteful; instead mark everything reachable from the border and invert.
function closedIslands(inputGrid) {
  const g = inputGrid.map(r => [...r]);
  const rows = g.length, cols = g[0].length;

  function flood(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || g[r][c] !== 0) return;
    g[r][c] = 2;                                  // reachable from outside
    flood(r + 1, c); flood(r - 1, c); flood(r, c + 1); flood(r, c - 1);
  }

  // Flood from every border cell.
  for (let r = 0; r < rows; r++) { flood(r, 0); flood(r, cols - 1); }
  for (let c = 0; c < cols; c++) { flood(0, c); flood(rows - 1, c); }

  // Whatever is still 0 is enclosed. Count the blobs.
  let closed = 0;
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (g[r][c] === 0) { closed++; (function sink(rr, cc) {
        if (rr < 0 || rr >= rows || cc < 0 || cc >= cols || g[rr][cc] !== 0) return;
        g[rr][cc] = 2;
        sink(rr + 1, cc); sink(rr - 1, cc); sink(rr, cc + 1); sink(rr, cc - 1);
      })(r, c); }
  return closed;
}

console.log(closedIslands([
  [1, 1, 1, 1, 1, 1, 1, 0],
  [1, 0, 0, 0, 0, 1, 1, 0],
  [1, 0, 1, 0, 1, 1, 1, 0],
  [1, 0, 0, 0, 0, 1, 0, 1],
  [1, 1, 1, 1, 1, 1, 1, 0],
]));   // 2
console.log(closedIslands([[0, 0], [0, 0]]));      // 0, everything touches the edge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35// Transpose, then reverse each row. Two simple steps beat one confusing formula.
function rotate(matrix) {
  const n = matrix.length;

  // Transpose: swap across the main diagonal. j starts at i + 1 so each pair
  // is swapped exactly once — starting at 0 would swap everything back.
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j < n; j++)
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];

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

const show = m => m.map(r => r.join(' ')).join('\n');

const m3 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
console.log('before:\n' + show(m3));
console.log('after: \n' + show(rotate(m3)));

const m2 = [[1, 2], [3, 4]];
console.log('2x2 rotated:\n' + show(rotate(m2)));

// Counter-clockwise is the same two steps in the other order:
// reverse the rows of the whole matrix, then transpose.
function rotateCCW(matrix) {
  const n = matrix.length;
  matrix.reverse();
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j < n; j++)
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
  return matrix;
}
console.log('counter-clockwise:\n' + show(rotateCCW([[1, 2, 3], [4, 5, 6], [7, 8, 9]])));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33function 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--;

    // These two need a re-check: a single remaining row or column would
    // otherwise be traversed twice.
    if (top <= bottom) {
      for (let c = right; c >= left; c--) result.push(matrix[bottom][c]); // ←
      bottom--;
    }
    if (left <= right) {
      for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);   // ↑
      left++;
    }
  }
  return result;
}

console.log(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]));
console.log(spiralOrder([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]));
console.log(spiralOrder([[1, 2, 3]]));          // single row
console.log(spiralOrder([[1], [2], [3]]));      // single column
console.log(spiralOrder([[7]]));                // single cell
console.log(spiralOrder([]));                   // empty

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26function setZeroes(matrix) {
  const rows = matrix.length, cols = matrix[0].length;
  let firstRowHasZero = false, firstColHasZero = false;

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

  // Record which rows and columns need clearing, in row 0 and column 0.
  for (let r = 1; r < rows; r++)
    for (let c = 1; c < cols; c++)
      if (matrix[r][c] === 0) { matrix[r][0] = 0; matrix[0][c] = 0; }

  // Apply, still skipping the first row and column.
  for (let r = 1; r < rows; r++)
    for (let c = 1; c < cols; c++)
      if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0;

  if (firstRowHasZero) for (let c = 0; c < cols; c++) matrix[0][c] = 0;
  if (firstColHasZero) for (let r = 0; r < rows; r++) matrix[r][0] = 0;
  return matrix;
}

const showMat = m => m.map(r => r.join(' ')).join('\n');
console.log(showMat(setZeroes([[1, 1, 1], [1, 0, 1], [1, 1, 1]])));
console.log('---');
console.log(showMat(setZeroes([[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]])));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38// Fully sorted, each row starting after the previous ends: index arithmetic
// maps a 1D position onto 2D coordinates.
function searchFullySorted(matrix, target) {
  const rows = matrix.length, cols = matrix[0].length;
  let lo = 0, hi = rows * cols - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    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;
}

// Rows and columns each sorted, but rows may overlap: start top-right and
// eliminate a whole row or column on every step.
function searchRowColSorted(matrix, target) {
  let r = 0, c = matrix[0].length - 1;
  while (r < matrix.length && c >= 0) {
    if (matrix[r][c] === target) return true;
    if (matrix[r][c] > target) c--;      // this column is all too big
    else r++;                            // this row is all too small
  }
  return false;
}

const sortedFully = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]];
console.log('binary search 16:', searchFullySorted(sortedFully, 16), '| 13:', searchFullySorted(sortedFully, 13));

const staircase = [
  [1, 4, 7, 11],
  [2, 5, 8, 12],
  [3, 6, 9, 16],
  [10, 13, 14, 17],
];
console.log('staircase 5: ', searchRowColSorted(staircase, 5));
console.log('staircase 20:', searchRowColSorted(staircase, 20));
console.log('rows*cols =', 3 * 4, 'so binary search is O(log 12); staircase is O(rows + cols)');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34// A single long corridor forces maximum recursion depth.
function floodRecursive(cells) {
  const g = [Array(cells).fill(1)];        // 1 row, `cells` columns
  function sink(c) {
    if (c < 0 || c >= cells || g[0][c] !== 1) return;
    g[0][c] = 0;
    sink(c + 1);
    sink(c - 1);
  }
  sink(0);
  return g[0].every(v => v === 0);
}

function floodIterative(cells) {
  const g = [Array(cells).fill(1)];
  const stack = [0];
  g[0][0] = 0;
  while (stack.length) {
    const c = stack.pop();
    for (const next of [c + 1, c - 1]) {
      if (next < 0 || next >= cells || g[0][next] !== 1) continue;
      g[0][next] = 0;
      stack.push(next);
    }
  }
  return g[0].every(v => v === 0);
}

for (const size of [100, 5000, 200000]) {
  let recursive;
  try { recursive = floodRecursive(size) ? 'ok' : 'incomplete'; }
  catch (err) { recursive = err.constructor.name; }
  console.log(`${String(size).padStart(6)} cells: recursive ${recursive.padEnd(11)} iterative ${floodIterative(size) ? 'ok' : 'incomplete'}`);
}