133. Clone Graph☆

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 ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const wordSet = new Set<string>(wordList);
  if (!wordSet.has(endWord)) return 0;

  // Build wildcard buckets: "h*t" -> ["hit","hot"]
  const buckets = new Map<string, string[]>();
  for (const word of [beginWord, ...wordList]) {
    for (let i = 0; i < word.length; i++) {
      const key = word.slice(0, i) + '*' + word.slice(i + 1);
      const list = buckets.get(key) ?? [];
      list.push(word);
      buckets.set(key, list);
    }
  }

  const visited = new Set<string>([beginWord]);
  const queue: string[] = [beginWord];
  let depth = 1;

  while (queue.length > 0) {
    depth++;
    const size = queue.length;
    for (let qi = 0; qi < size; qi++) {
      const word = queue.shift()!;
      for (let i = 0; i < word.length; i++) {
        const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
        for (const neighbor of buckets.get(pattern) ?? []) {
          if (neighbor === endWord) return depth;
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
          }
        }
      }
    }
  }

  return 0; // endWord unreachable
}

function solve(board: string[][]): void {
  const rows = board.length;
  const cols = board[0]?.length ?? 0;

  // DFS from a border cell, marking every reachable 'O' as safe ('S').
  function dfs(r: number, c: number): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (board[r][c] !== 'O') return;
    board[r][c] = 'S';           // mark safe
    dfs(r - 1, c);
    dfs(r + 1, c);
    dfs(r, c - 1);
    dfs(r, c + 1);
  }

  // 1. Seed DFS from every 'O' on the four edges.
  for (let r = 0; r < rows; r++) {
    dfs(r, 0);
    dfs(r, cols - 1);
  }
  for (let c = 0; c < cols; c++) {
    dfs(0, c);
    dfs(rows - 1, c);
  }

  // 2. Flip: 'O' → 'X' (surrounded), 'S' → 'O' (restore safe).
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === 'O') board[r][c] = 'X';
      else if (board[r][c] === 'S') board[r][c] = 'O';
    }
  }
}

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)!;
}