Second Minimum Time to Reach Destination

Hard

#1862Time: O(N * E) in the worst case. A vertex can be enqueued multiple times if better paths are found. This is characteristic of SPFA-like algorithms and can be much slower than Dijkstra's on certain graphs.Space: O(N + E), where N is the number of vertices and E is the number of edges. This is for storing the adjacency list, distance arrays, and the queue. In the worst case, the queue can hold a large number of states.

Algorithms

Breadth-First Search Shortest Path

Data structures

Graph

Prompt

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] = [u_i, v_i] denotes a bi-directional edge between vertex u_i and vertex v_i. 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.

For example the second minimum value of [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:

You can go through any vertex any number of times, including 1 and n.
You can assume that when the journey starts, all signals have just turned green.

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 <= 10⁴
n - 1 <= edges.length <= min(2 * 10⁴, n * (n - 1) / 2)
edges[i].length == 2
1 <= u_i, v_i <= n
u_i != v_i
There are no duplicate edges.
Each vertex can be reached directly or indirectly from every other vertex.
1 <= time, change <= 10³

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a modified Breadth-First Search (BFS) to explore the graph. Since the edge weights (travel times) are not uniform due to potential waiting times at traffic signals, a standard BFS on nodes is insufficient. Instead, we perform a search on the state space (vertex, time). We maintain two arrays, dist1 and dist2, to keep track of the minimum and second minimum time to reach each vertex. A standard queue is used to manage the states to visit. While functionally correct, this method can be inefficient as it doesn't prioritize exploring paths with shorter total times, which can lead to exploring many suboptimal paths.

Algorithm

Graph Representation: Build an adjacency list to represent the city's connections.
Distance Arrays: Initialize two arrays, dist1 and dist2, of size n+1. dist1[i] will store the minimum time to reach vertex i, and dist2[i] will store the second minimum time. Initialize all values to infinity, except for dist1[1] = 0.
Queue Initialization: Use a standard queue (e.g., LinkedList) and add the starting state, which is vertex 1 at time 0: (1, 0).
BFS Traversal: While the queue is not empty, dequeue a state (u, currentTime).
Calculate Arrival Time at Neighbors: For the current vertex u and currentTime: a. Determine if you need to wait for a green light. The signal is green during intervals [0, change), [2*change, 3*change), etc. If (currentTime / change) is odd, the light is red, and you must wait until the time is (currentTime / change + 1) * change. b. Calculate the newTime to reach a neighbor v as departureTime + time.
Update Distances and Enqueue: For each neighbor v of u: a. If newTime is less than dist1[v], you've found a new shortest path. Update dist1[v] = newTime and the old dist1[v] becomes the new dist2[v]. Enqueue the new state (v, newTime). b. If newTime is greater than dist1[v] but less than dist2[v], you've found a new second shortest path. Update dist2[v] = newTime and enqueue (v, newTime).
Result: After the queue is empty, dist2[n] will contain the second minimum time to reach the destination.

Walkthrough

This method adapts the BFS algorithm, which is typically used for unweighted graphs, to solve this problem. The state in our search is a pair (vertex, time). We use a queue to process these states in a first-in, first-out manner.

We maintain two arrays, dist1 and dist2, to store the shortest and second shortest times to every vertex. Initially, dist1[1] is 0, and all other distances are infinity.

We start by pushing (1, 0) into the queue. In each step, we extract a (vertex, time) pair, calculate the time to reach its neighbors (including waiting for green lights), and update the dist1 and dist2 arrays if we find a shorter or a new second-shorter path. If an update occurs, the new (neighbor, newTime) state is added to the queue.

This process is similar to the Shortest Path Faster Algorithm (SPFA). Its main drawback is that it might re-process vertices many times if shorter paths are discovered late in the search, making its worst-case performance poor compared to Dijkstra's algorithm.

1import java.util.*;2 3class Solution {4    public int secondMinimum(int n, int[][] edges, int time, int change) {5        List<List<Integer>> adj = new ArrayList<>();6        for (int i = 0; i <= n; i++) {7            adj.add(new ArrayList<>());8        }9        for (int[] edge : edges) {10            adj.get(edge[0]).add(edge[1]);11            adj.get(edge[1]).add(edge[0]);12        }13 14        int[] dist1 = new int[n + 1];15        int[] dist2 = new int[n + 1];16        Arrays.fill(dist1, Integer.MAX_VALUE);17        Arrays.fill(dist2, Integer.MAX_VALUE);18 19        Queue<int[]> q = new LinkedList<>();20        q.offer(new int[]{1, 0}); // {node, time}21        dist1[1] = 0;22 23        while (!q.isEmpty()) {24            int[] curr = q.poll();25            int u = curr[0];26            int currentTime = curr[1];27 28            int waitTime = 0;29            if ((currentTime / change) % 2 == 1) { // Red light30                waitTime = change - (currentTime % change);31            }32            int newTime = currentTime + waitTime + time;33 34            for (int v : adj.get(u)) {35                if (newTime < dist1[v]) {36                    dist2[v] = dist1[v];37                    dist1[v] = newTime;38                    q.offer(new int[]{v, newTime});39                } else if (dist1[v] < newTime && newTime < dist2[v]) {40                    dist2[v] = newTime;41                    q.offer(new int[]{v, newTime});42                }43            }44        }45        return dist2[n];46    }47}

Complexity

Time

O(N * E) in the worst case. A vertex can be enqueued multiple times if better paths are found. This is characteristic of SPFA-like algorithms and can be much slower than Dijkstra's on certain graphs.

Space

O(N + E), where N is the number of vertices and E is the number of edges. This is for storing the adjacency list, distance arrays, and the queue. In the worst case, the queue can hold a large number of states.

Trade-offs

Pros

Conceptually simpler than Dijkstra's algorithm as it uses a basic queue data structure.
Relatively easy to implement.

Cons

Can be significantly less efficient than a priority-queue-based approach, potentially leading to a 'Time Limit Exceeded' error on larger or more complex graph structures.
It may explore many redundant paths because it doesn't prioritize states with lower travel times, leading to re-computation when a shorter path to an already visited node is found later.

This approach adapts Dijkstra's algorithm, which is ideal for finding the shortest paths in a graph with non-negative edge weights. The key is to use a priority queue to always expand the search from the vertex that can be reached in the minimum amount of time so far. This ensures that we find the shortest path to each vertex first. To find the second minimum time, we augment the algorithm to keep track of the two shortest times (dist1 and dist2) to reach each vertex. By processing states in increasing order of time, this method efficiently prunes the search space and avoids the redundant computations of the BFS-based approach.

Algorithm

Graph Representation: Build an adjacency list for the graph.
Distance Arrays: Initialize dist1 and dist2 arrays to store the minimum and second minimum times for each vertex. Set all to infinity, except dist1[1] = 0.
Priority Queue: Use a priority queue to store states (vertex, time), ordered by time. Add the starting state (1, 0).
Dijkstra's Traversal: While the priority queue is not empty, extract the state (u, currentTime) with the smallest time.
Pruning: If currentTime is already greater than dist2[u], we can skip this state, as we've already found two better or equal paths to u.
Early Exit (Optional but efficient): If u is the destination n and we have found a time for it that is strictly greater than dist1[n], this must be the second minimum time, so we can return it.
Calculate Arrival Time: As in the BFS approach, calculate the departureTime from u considering traffic signal waits, and then the newTime to reach a neighbor v.
Update and Enqueue: For each neighbor v of u: a. If newTime < dist1[v], update dist1[v] and dist2[v], and push the new state (v, newTime) to the priority queue. b. If dist1[v] < newTime < dist2[v], update dist2[v] and push (v, newTime) to the priority queue.
Result: The algorithm will find dist2[n], which is the answer.

Walkthrough

This is the most efficient and standard way to solve this kind of shortest path problem. We model the problem on a graph where the nodes are the vertices and edge weights are dynamic based on arrival times.

Dijkstra's algorithm uses a priority queue to guarantee that we always explore the path with the currently known minimum total time. This is crucial for efficiency. We modify it to find two distinct shortest paths.

We maintain dist1 and dist2 arrays. The priority queue stores (vertex, time) pairs and prioritizes those with the smallest time. We start with (1, 0).

When we extract a state (u, currentTime) from the priority queue, we know that currentTime is the shortest possible time for one of the paths to u among all paths not yet finalized. We then calculate the time to reach its neighbors. If this newTime offers a better dist1 or dist2 for a neighbor v, we update the distances and add (v, newTime) to the priority queue. A key optimization is to ignore any state (u, currentTime) if currentTime > dist2[u], as we have already found two shorter paths to u.

Once we extract the destination n from the priority queue for the second time with a distinct time value, that time is our answer.

1import java.util.*;2 3class Solution {4    public int secondMinimum(int n, int[][] edges, int time, int change) {5        List<List<Integer>> adj = new ArrayList<>();6        for (int i = 0; i <= n; i++) {7            adj.add(new ArrayList<>());8        }9        for (int[] edge : edges) {10            adj.get(edge[0]).add(edge[1]);11            adj.get(edge[1]).add(edge[0]);12        }13 14        int[] dist1 = new int[n + 1];15        int[] dist2 = new int[n + 1];16        Arrays.fill(dist1, Integer.MAX_VALUE);17        Arrays.fill(dist2, Integer.MAX_VALUE);18 19        // PriorityQueue stores {node, time}20        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);21        pq.offer(new int[]{1, 0});22        dist1[1] = 0;23 24        while (!pq.isEmpty()) {25            int[] curr = pq.poll();26            int u = curr[0];27            int currentTime = curr[1];28 29            if (u == n && dist2[n] != Integer.MAX_VALUE) {30                return dist2[n];31            }32 33            // If we have already found two shorter paths to u, skip34            if (currentTime > dist2[u]) {35                continue;36            }37 38            // Calculate departure time considering traffic light39            int waitTime = 0;40            if ((currentTime / change) % 2 == 1) { // Red light41                waitTime = change - (currentTime % change);42            }43            int newTime = currentTime + waitTime + time;44 45            for (int v : adj.get(u)) {46                if (newTime < dist1[v]) {47                    dist2[v] = dist1[v];48                    dist1[v] = newTime;49                    pq.offer(new int[]{v, newTime});50                } else if (dist1[v] < newTime && newTime < dist2[v]) {51                    dist2[v] = newTime;52                    pq.offer(new int[]{v, newTime});53                }54            }55        }56        return -1; // Should not be reached57    }58}

Complexity

Time

O(E log N). Each edge relaxation may add an item to the priority queue. Since we only process each node for its first and second shortest paths, the number of pushes is proportional to E. Each priority queue operation takes O(log N) or O(log E) time.

Space

O(N + E), where N is the number of vertices and E is the number of edges. This space is used for the adjacency list, distance arrays, and the priority queue.

Trade-offs

Pros

Highly efficient and guaranteed to find the optimal solution.
The use of a priority queue effectively prunes the search space, avoiding redundant calculations.

Cons

Slightly more complex to implement due to the use of a priority queue.
The logic for handling two distances per node adds a small amount of overhead compared to a standard Dijkstra's implementation.

Solutions

Solution

1class Solution {2public3  int secondMinimum(int n, int[][] edges, int time, int change) {4    List<Integer>[] g = new List[n + 1];5    Arrays.setAll(g, k->new ArrayList<>());6    for (int[] e : edges) {7      int u = e[0], v = e[1];8      g[u].add(v);9      g[v].add(u);10    }11    Deque<int[]> q = new LinkedList<>();12    q.offerLast(new int[]{1, 0});13    int[][] dist = new int[n + 1][2];14    for (int i = 0; i < n + 1; ++i) {15      Arrays.fill(dist[i], Integer.MAX_VALUE);16    }17    dist[1][1] = 0;18    while (!q.isEmpty()) {19      int[] e = q.pollFirst();20      int u = e[0], d = e[1];21      for (int v : g[u]) {22        if (d + 1 < dist[v][0]) {23          dist[v][0] = d + 1;24          q.offerLast(new int[]{v, d + 1});25        } else if (dist[v][0] < d + 1 && d + 1 < dist[v][1]) {26          dist[v][1] = d + 1;27          if (v == n) {28            break;29          }30          q.offerLast(new int[]{v, d + 1});31        }32      }33    }34    int ans = 0;35    for (int i = 0; i < dist[n][1]; ++i) {36      ans += time;37      if (i < dist[n][1] - 1 && (ans / change) % 2 == 1) {38        ans = (ans + change) / change * change;39      }40    }41    return ans;42  }43}

1class Solution:2    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int: g = defaultdict(set) for u, v in edges: g[u]. add(v) g[v]. add(u) q = deque([(1, 0)]) dist = [[inf] * 2 for _ in range(n + 1)] dist[1][1] = 0 while q: u, d = q . popleft() for v in g[u]: if d + 1 < dist[v][0]: dist[v][0] = d + 1 q . append((v, d + 1)) elif dist[v][0] < d + 1 < dist[v][1]: dist[v][1] = d + 1 if v == n: break q . append((v, d + 1)) ans = 0 for i in range(dist[n][1]): ans += time if i < dist[n][1] - 1 and (ans // change) % 2 == 1: ans = (ans + change) // change * change return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem