207. Course Schedule☆

function pacificAtlantic(heights: number[][]): number[][] {
  const R = heights.length, C = heights[0].length;
  const pacific  = new Set<number>();
  const atlantic = new Set<number>();
  const idx = (r: number, c: number) => r * C + c;

  function dfs(r: number, c: number, reach: Set<number>): void {
    if (reach.has(idx(r, c))) return;
    reach.add(idx(r, c));
    const dirs: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
      if (reach.has(idx(nr, nc))) continue;
      if (heights[nr][nc] >= heights[r][c]) dfs(nr, nc, reach);
    }
  }

  // Seed Pacific: top row + left column
  for (let c = 0; c < C; c++) dfs(0, c, pacific);
  for (let r = 1; r < R; r++) dfs(r, 0, pacific);

  // Seed Atlantic: bottom row + right column
  for (let c = 0; c < C; c++) dfs(R - 1, c, atlantic);
  for (let r = 0; r < R - 1; r++) dfs(r, C - 1, atlantic);

  // Intersection
  const result: number[][] = [];
  for (let r = 0; r < R; r++)
    for (let c = 0; c < C; c++)
      if (pacific.has(idx(r, c)) && atlantic.has(idx(r, c)))
        result.push([r, c]);
  return result;
}

function networkDelayTime(times: number[][], n: number, k: number): number {
  // Build adjacency list: src -> [(dst, weight)]
  const adj = new Map<number, [number, number][]>();
  for (let i = 1; i <= n; i++) adj.set(i, []);
  for (const [u, v, w] of times) {
    adj.get(u)!.push([v, w]);
  }

  // Min-heap ordered by (dist, node). Encode as [dist, node].
  const dist = new Map<number, number>();
  // Simple min-heap via sorted array (replace with binary heap for production)
  const heap: [number, number][] = [[0, k]];

  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]);
    const [d, u] = heap.shift()!;
    if (dist.has(u)) continue;   // already finalized
    dist.set(u, d);
    for (const [v, w] of (adj.get(u) ?? [])) {
      if (!dist.has(v)) {
        heap.push([d + w, v]);
      }
    }
  }

  if (dist.size !== n) return -1;
  return Math.max(...dist.values());
}

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  // Build adjacency list and indegree counter
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  const indegree: number[] = new Array(numCourses).fill(0);

  for (const [a, b] of prerequisites) {
    adj[b].push(a);   // b must be taken before a  =>  edge b -> a
    indegree[a]++;
  }

  // Seed the queue with all courses that have no prerequisites
  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  let finished = 0;
  while (queue.length > 0) {
    const cur = queue.shift()!;
    finished++;
    for (const neighbor of adj[cur]) {
      indegree[neighbor]--;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  // If every course was processed there is no cycle
  return finished === numCourses;
}

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