994. Rotting Oranges☆

function minCostConnectPoints(points: number[][]): number {
  const n = points.length;
  if (n <= 1) return 0;

  // inMST[i] = true once node i has been added to the spanning tree
  const inMST = new Array<boolean>(n).fill(false);

  // minEdge[i] = cheapest known edge cost to connect node i into the MST
  const minEdge = new Array<number>(n).fill(Infinity);
  minEdge[0] = 0; // start from node 0 at cost 0

  // Min-heap entries: [cost, nodeIndex]
  // Using a simple array-based binary heap
  const heap: [number, number][] = [[0, 0]];
  let totalCost = 0;
  let edgesAdded = 0;

  const heapPush = (cost: number, node: number): void => {
    heap.push([cost, node]);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p][0] <= heap[i][0]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };

  const heapPop = (): [number, number] => {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let s = i;
        if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
        if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
        if (s === i) break;
        [heap[i], heap[s]] = [heap[s], heap[i]];
        i = s;
      }
    }
    return top;
  };

  while (heap.length > 0 && edgesAdded < n) {
    const [cost, u] = heapPop();

    if (inMST[u]) continue; // stale heap entry — skip
    inMST[u] = true;
    totalCost += cost;
    edgesAdded++;

    for (let v = 0; v < n; v++) {
      if (!inMST[v]) {
        const d = Math.abs(points[u][0] - points[v][0])
                + Math.abs(points[u][1] - points[v][1]);
        if (d < minEdge[v]) {
          minEdge[v] = d;
          heapPush(d, v);
        }
      }
    }
  }

  return totalCost;
}

function findRedundantConnection(edges: number[][]): number[] {
  const parent: number[] = Array.from({ length: edges.length + 1 }, (_, i) => i);

  function find(x: number): number {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path-compression (halving)
      x = parent[x];
    }
    return x;
  }

  for (const [u, v] of edges) {
    const ru = find(u);
    const rv = find(v);
    if (ru === rv) return [u, v];   // both already in same component → cycle
    parent[ru] = rv;                // union: attach ru's tree under rv
  }

  return []; // unreachable given valid input
}

class _Node {
  val: number;
  neighbors: _Node[];
  constructor(val = 0, neighbors: _Node[] = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

function cloneGraph(node: _Node | null): _Node | null {
  if (!node) return null;

  // Map from original node → its deep clone.
  // It serves two roles at once: visited set AND clone registry.
  const cloneMap = new Map<_Node, _Node>();

  const queue: _Node[] = [node];
  cloneMap.set(node, new _Node(node.val));

  while (queue.length > 0) {
    const cur = queue.shift()!;
    const curClone = cloneMap.get(cur)!;

    for (const neighbor of cur.neighbors) {
      if (!cloneMap.has(neighbor)) {
        // First visit: create the clone and enqueue the original.
        cloneMap.set(neighbor, new _Node(neighbor.val));
        queue.push(neighbor);
      }
      // Whether brand-new or already seen, wire the edge.
      curClone.neighbors.push(cloneMap.get(neighbor)!);
    }
  }

  return cloneMap.get(node)!;
}

function orangesRotting(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const queue: [number, number][] = [];
  let fresh = 0;

  // Seed: enqueue ALL initially rotten cells at once (multi-source BFS)
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }
  }

  if (fresh === 0) return 0;   // nothing to rot

  const dirs: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
  let minutes = 0;
  let head = 0;   // pointer into queue (avoids O(n) shift)

  while (head < queue.length) {
    const layerSize = queue.length - head;   // all cells in current minute
    for (let i = 0; i < layerSize; i++) {
      const [r, c] = queue[head++];
      for (const [dr, dc] of dirs) {
        const nr = r + dr;
        const nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
          grid[nr][nc] = 2;   // mark rotten in-place (visited)
          fresh--;
          queue.push([nr, nc]);
        }
      }
    }
    minutes++;
  }

  return fresh === 0 ? minutes - 1 : -1;
}