Second Minimum Time to Reach Destination

Second Minimum Time to Reach Destination

What is this problem about?

The Second Minimum Time to Reach Destination interview question gives you a graph with n nodes and undirected edges, where traversal follows traffic signal timing. Each edge takes time minutes to traverse. Signals switch every change minutes (between green and red). You cannot start traversal on a red signal. Find the second minimum time to reach node n from node 1. The path may revisit nodes and edges.

Why is this asked in interviews?

Microsoft, Amazon, and Google ask this HARD graph problem because it combines BFS with signal-aware state transitions and requires finding the second minimum path — not just the shortest. It models real-world traffic network optimization where timing constraints (traffic lights) affect routing. It tests BFS on weighted graphs, state augmentation (tracking visit count per node), and signal phase calculation.

Algorithmic pattern used

The pattern is BFS with augmented state tracking. Track each node's first and second minimum arrival times using an array dist[node][0] (first min time) and dist[node][1] (second min time). Run BFS: for each state (node, arrival time), compute the actual departure time by adjusting for signal phase — if currently in a red phase, wait until the next green. Add time to get the new arrival. Update dist[neighbor][0] or dist[neighbor][1] if the new arrival improves either. Stop when dist[n][1] is set.

Example explanation

Graph: 1—2—3—4, also 1—3. time=3, change=5.

Shortest path 1→3→4: time=6. Red at t=6 (in second red phase [5,10])→wait until t=10. Arrive at 4 at t=13. Second shortest may revisit: 1→2→1→3→4 or 1→3→1→3→4. The second minimum arrival gives t=13.

Common mistakes candidates make

• Using standard Dijkstra without tracking the second minimum — Dijkstra finds the shortest path but not the second shortest.
• Not computing signal wait time correctly: phase = arrival_time // change; if phase % 2 == 1: departure = (phase + 1) * change; else departure = arrival_time.
• Assuming the second minimum path cannot revisit nodes — it can, and sometimes must.
• Pruning states that equal the first minimum time — these are needed to find the second minimum.

Interview preparation tip

For the Second Minimum Time to Reach Destination coding problem, the BFS shortest path graph interview pattern with state augmentation is the approach. The critical insight: BFS can find the second minimum time by allowing each node to be visited twice (once for the first minimum, once for the second). Google interviewers appreciate the signal phase formula being explained before coding. Practice this "second minimum path" pattern — it generalizes to k-shortest path algorithms used in navigation systems.