Second Minimum Time to Reach Destination

Problem (restated)

An undirected unweighted graph on nodes 1…n. Traversing any edge takes time minutes. Each node has a traffic light: change minutes green, then change minutes red, starting green at t=0. You may leave a node only while green (wait if you arrive on red). Return the second-minimum arrival time at n from 1.

Intuition

You need two distinct arrival times at n, so each node stores a first and a second time (strictly larger). Dijkstra/BFS keyed by arrival. Before leaving, if ⌊t / change⌋ is odd, wait until the next green: t += change - t % change. Then every neighbor arrives at t + time.

Approaches

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * Each node keeps first and second arrival; leave only on green.
 */
export function secondMinimum(
  n: number,
  edges: number[][],
  time: number,
  change: number,
): number {
  const adj: number[][] = Array.from({ length: n + 1 }, () => []);
  for (const [a, b] of edges) {
    adj[a]!.push(b);
    adj[b]!.push(a);
  }
  const dist1 = new Array<number>(n + 1).fill(Infinity);
  const dist2 = new Array<number>(n + 1).fill(Infinity);
  dist1[1] = 0;
  const pq: [number, number][] = [[0, 1]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    let [t, u] = pq.shift()!;
    if (u === n && t > dist1[n]!) return t;
    if (Math.floor(t / change) % 2 === 1) t += change - (t % change);
    for (const v of adj[u]!) {
      const nt = t + time;
      if (nt < dist1[v]!) {
        dist2[v] = dist1[v]!;
        dist1[v] = nt;
        pq.push([nt, v]);
      } else if (nt > dist1[v]! && nt < dist2[v]!) {
        dist2[v] = nt;
        pq.push([nt, v]);
      }
    }
  }
  return dist2[n]!;
}

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * Each node keeps first and second arrival; leave only on green.
 */
export function secondMinimum(
  n: number,
  edges: number[][],
  time: number,
  change: number,
): number {
  const adj: number[][] = Array.from({ length: n + 1 }, () => []);
  for (const [a, b] of edges) {
    adj[a]!.push(b);
    adj[b]!.push(a);
  }
  const dist1 = new Array<number>(n + 1).fill(Infinity);
  const dist2 = new Array<number>(n + 1).fill(Infinity);
  dist1[1] = 0;
  const pq: [number, number][] = [[0, 1]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    let [t, u] = pq.shift()!;
    if (u === n && t > dist1[n]!) return t;
    if (Math.floor(t / change) % 2 === 1) t += change - (t % change);
    for (const v of adj[u]!) {
      const nt = t + time;
      if (nt < dist1[v]!) {
        dist2[v] = dist1[v]!;
        dist1[v] = nt;
        pq.push([nt, v]);
      } else if (nt > dist1[v]! && nt < dist2[v]!) {
        dist2[v] = nt;
        pq.push([nt, v]);
      }
    }
  }
  return dist2[n]!;
}

Template connection

Dijkstra + extra state, here a second distance per node instead of (node, k). Same “do not stop at first pop” idea as LC 787.

Reflection

• Keep dist1 and dist2. A candidate smaller than the first arrival shifts the first down. A time strictly between them becomes the second. An equal time is not a second arrival.
• The answer is the first time you pop n with t > dist1[n]. That pop is the arrival.
• The light is checked on departure: if t // change is odd, wait change - t % change before leaving. n = 2 is the direct edge.