Watch 10 video solutions for Second Minimum Time to Reach Destination, a hard level problem involving Breadth-First Search, Graph, Shortest Path. This walkthrough by NeetCodeIO has 12,195 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A city is represented as a bi-directional connected graph with n vertices where each vertex is labeled from 1 to n (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. The time taken to traverse any edge is time minutes.
Each vertex has a traffic signal which changes its color from green to red and vice versa every change minutes. All signals change at the same time. You can enter a vertex at any time, but can leave a vertex only when the signal is green. You cannot wait at a vertex if the signal is green.
The second minimum value is defined as the smallest value strictly larger than the minimum value.
[2, 3, 4] is 3, and the second minimum value of [2, 2, 4] is 4.Given n, edges, time, and change, return the second minimum time it will take to go from vertex 1 to vertex n.
Notes:
1 and n.
Example 1:
Input: n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5 Output: 13 Explanation: The figure on the left shows the given graph. The blue path in the figure on the right is the minimum time path. The time taken is: - Start at 1, time elapsed=0 - 1 -> 4: 3 minutes, time elapsed=3 - 4 -> 5: 3 minutes, time elapsed=6 Hence the minimum time needed is 6 minutes. The red path shows the path to get the second minimum time. - Start at 1, time elapsed=0 - 1 -> 3: 3 minutes, time elapsed=3 - 3 -> 4: 3 minutes, time elapsed=6 - Wait at 4 for 4 minutes, time elapsed=10 - 4 -> 5: 3 minutes, time elapsed=13 Hence the second minimum time is 13 minutes.
Example 2:
Input: n = 2, edges = [[1,2]], time = 3, change = 2 Output: 11 Explanation: The minimum time path is 1 -> 2 with time = 3 minutes. The second minimum time path is 1 -> 2 -> 1 -> 2 with time = 11 minutes.
Constraints:
2 <= n <= 104n - 1 <= edges.length <= min(2 * 104, n * (n - 1) / 2)edges[i].length == 21 <= ui, vi <= nui != vi1 <= time, change <= 103Problem Overview: You are given an undirected graph where each edge takes the same travel time, but intersections have traffic signals that alternate between green and red every change minutes. The goal is to reach node n from node 1, not with the shortest travel time, but with the second minimum arrival time while respecting signal delays.
Approach 1: Breadth-First Search with Traffic Signal Simulation (Time: O(E), Space: O(V))
This approach uses Breadth-First Search on the graph while tracking the first and second arrival times for every node. Instead of storing only one distance, maintain two values: the shortest and second shortest arrival time. Each time you move along an edge, compute whether you must wait for the signal. If the current time falls in a red phase ((time / change) % 2 == 1), wait until the next green phase before traveling. Push new arrival times into the BFS queue only if they improve the first or second best time for that node. The algorithm stops once the second arrival time for node n is discovered.
The key insight is that BFS works because all edges have equal traversal time. The additional logic handles signal waiting and ensures each node records up to two unique arrival times.
Approach 2: Modified Dijkstra's Algorithm (Time: O(E log V), Space: O(V))
This method models the problem as a shortest path search where each node can be visited twice with different arrival times. Use a priority queue to always expand the smallest current time. When exploring neighbors, calculate the departure time considering signal cycles: if the light is red, wait until the next green interval before adding edge travel time. Maintain two best arrival times per node and ignore any candidate that is not among the top two.
The modified Dijkstra structure guarantees correct ordering of times, which simplifies reasoning about when the second minimum path is finalized. It works well when you want strict ordering of states and deterministic expansion of earliest arrival times.
Recommended for interviews: The BFS-based solution is usually preferred because all edges have equal weight. Interviewers expect you to recognize that this is a graph traversal problem with multiple valid distances per node. Showing the two-distance tracking technique demonstrates strong understanding of BFS and shortest-path variations, while the Dijkstra variant proves you can generalize the idea when edge weights or timing rules become more complex.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search with Signal Simulation | O(E) | O(V) | Best when all edges have equal travel time and you only need the first and second arrival times. |
| Modified Dijkstra's Algorithm | O(E log V) | O(V) | Useful when reasoning about ordered arrival times or when extending to weighted edges. |