2045. Second Minimum Time to Reach Destination


Problem Description

The city is modeled as a graph with n vertices, or points, which stand for different places within the city. The connections between these points are represented by bi-directional edges, which imply that one can travel in either direction between any two connected points. The set of these connections is given by an array of edge pairs, edges, where each pair [u_i, v_i] indicates a direct path between the vertices labeled u_i and v_i.

Travel time on any edge is constant, represented by the time variable. Importantly, the vertices in this city have traffic signals that toggle between green and red at fixed intervals given by the change variable. When a signal is green, one can leave the vertex, but they cannot do so during a red light, nor can they remain at the vertex waiting for it to turn green.

The task is to determine the second minimum time it takes to travel from vertex 1 to vertex n. The second minimum time is defined as the smallest value that is larger than the minimum travel time. Note that the travel is described with the following conditions:

  • Multiple passes through any vertex are permitted, including the start and end points.
  • The journey commences with all signals just turning green.

Given the setup of the graph (n and edges), the time taken to cross an edge (time), and the signal switching interval (change), the objective is to compute the second fastest time one can get from point 1 to point n.

Intuition

The solution approach involves the use of a breadth-first search (BFS) algorithm, which is typically used for finding the shortest path in a graph. For this problem, however, we need to consider traffic signals' timings while traversing the graph, hence a modification of the standard BFS.

In this solution, a graph g is constructed from the edges list where each vertex points to its set of adjacent vertices. The dist list holds the shortest and second shortest number of edges needed to reach every vertex from the starting vertex. The BFS is initiated from vertex 1.

The primary intuition here revolves around capturing the shortest and second shortest paths to each vertex. In a typical BFS, only the shortest path is considered, but due to our second minimum value requirement, we maintain two path lengths for each vertex. The BFS explores the graph, constantly updating these path lengths.

After the BFS traversal, we compute the actual time considering traffic signals. Since we have captured the number of edges traversed on the second shortest path to vertex n, we multiply this number by time to get the base travel time. However, due to the signal switching, we may have to wait at certain points if the signal is red when we arrive. This is modeled in the code by checking if the elapsed time is in a red signal interval. If it's a red signal, we wait until it turns green before continuing our journey.

To summarize, the solution consists of conducting a modified BFS to determine the second shortest path by the number of edges crossed, then converting this path length into actual time by taking into account the traffic signal intervals.

Learn more about Breadth-First Search, Graph and Shortest Path patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which type of traversal does breadth first search do?

Solution Approach

To execute our solution, we utilize a Breadth-First Search (BFS) algorithm with a slight twist to account for the traffic signals. Here is an explanation of how the provided Python code implements the solution:

  • First, we use a defaultdict to create a graph g where each vertex u has a set of its neighbors v. This represents our bi-directional graph.

  • We initialize a double-ended queue (deque) called q that will keep track of vertices to visit, starting with vertex 1. Each item in this queue will be a tuple containing a vertex and the number of edges crossed to reach it.

  • The dist array is initialized to hold the smallest and second smallest number of edges required to reach each vertex, starting from inf (infinity). For vertex 1, the distance is set to 0 since we start there.

  • The BFS begins by iterating through the queue q. At each step:

    • We pop the leftmost item (u, d) from the queue.
    • u represents the current vertex, while d is the distance (edge count) from vertex 1.
    • We then iterate through each neighbor v of the current vertex u.
    • For each neighbor v, we check whether we've found a shorter path (fewer edges) to reach it (d + 1 < dist[v][0]). If so, we update the shortest distance dist[v][0] and enqueue (v, d + 1) for further exploration.
    • If the shortest path is already found but the second shortest isn't (dist[v][0] < d + 1 < dist[v][1]), we update the second shortest distance dist[v][1] and, unless we're at the destination vertex n, we enqueue (v, d + 1).
  • Upon completion of the BFS, we compute the actual time taken to travel on the second shortest path using traffic signals consideration. The variable ans represents this time.

    • We iterate i from 0 to one less than the second shortest distance dist[n][1] (the number of edges in the second shortest path).
    • For each edge, we increase ans by time.
    • After traveling each edge, except the last one, we check if the signal would be red ((ans // change) % 2 == 1). If so, we wait for the next green (ans = (ans + change) // change * change).
  • Finally, ans holds the second minimum time it takes to go from vertex 1 to vertex n considering all traffic signals, which we return.

The key data structures used include:

  • A graph built as a dictionary of sets, providing efficient lookups and neighbor traversal.
  • A double-ended queue facilitating BFS.
  • A list of lists, dist, for tracking the shortest and second shortest paths to vertices.

This solution utilizes BFS for path exploration and leverages arithmetic to manage time spent waiting at traffic signals. The pairing of graph traversal with time management based on the graph's constraints makes it an elegant solution to the problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth first search?

Example Walkthrough

Let's illustrate the solution approach with a small example:

Assume we have the following setup:

  • A city with n = 4 vertices.
  • Connections between them: edges = [[1, 2], [2, 3], [3, 4], [1, 4]].
  • Constant travel time on any edge: time = 2 seconds.
  • Traffic signals toggle interval: change = 3 seconds.

The city graph will look like this:

11 -- 2
2|    |
34 -- 3

Vertex 1 is our starting point, and 4 is our destination.

Initial Setup

We construct the graph g using the edges:

1g = {
2  1: {2, 4},
3  2: {1, 3},
4  3: {2, 4},
5  4: {1, 3}
6}

The distance array dist is initialized as:

1dist = [
2  [inf, inf],  # Vertex 1
3  [inf, inf],  # Vertex 2
4  [inf, inf],  # Vertex 3
5  [inf, inf]   # Vertex 4
6]

And updated for vertex 1 as dist[0] = [0, inf], meaning the shortest distance to vertex 1 is 0 edges, and the second shortest is not yet found.

BFS Exploration

We enqueue vertex 1 with a distance of 0 into the queue q.

Dequeueing 1, we observe its neighbors are 2 and 4. We visit vertex 2 first, noting a distance of 1 edge. Since dist[2][0] is inf, we update it to 1. The same is done for vertex 4.

Now our dist looks like this:

1dist = [
2  [0, inf],  # Vertex 1
3  [1, inf],  # Vertex 2
4  [inf, inf],  # Vertex 3
5  [1, inf]   # Vertex 4
6]

In our queue, we now have vertices 2 and 4, both with distances of 1.

Continuing BFS, we dequeue 2 and then 4. Both have 3 as a common neighbor, which we reach with 2 edges. dist[3][0] becomes 2. From 3, we can reach 4 with 3 edges, updating dist[4][1] to 3.

Now our dist looks like this:

1dist = [
2  [0, inf],  # Vertex 1
3  [1, inf],  # Vertex 2
4  [2, inf],  # Vertex 3
5  [1, 3]   # Vertex 4
6]

This finalizes the BFS as we've found both the shortest (1 edge) and second-shortest (3 edges) paths to vertex 4.

Actual Time Computation

The shortest path to vertex 4 takes 1 edge, which at 2 seconds per edge, would take 2 seconds without signal delays.

The second shortest path takes 3 edges, which base time is 3 * 2 = 6 seconds.

Before crossing each edge except the last one, we consider the signal's state. On the second shortest path, for each edge:

  • At 0 seconds, we're at vertex 1.
  • After the first edge, 2 seconds have passed. No wait time is needed.
  • Arriving at vertex 3, 4 seconds have passed. The signal state alternates every 3 seconds, so we wait 2 more seconds for the next green signal.
  • After the second edge, 6 + 2 = 8 seconds have passed. Again, no wait is needed because we depart at the start of a green signal cycle.
  • Arriving at vertex 4, 10 seconds have passed, and no further wait is needed.

The second minimum time to go from vertex 1 to vertex 4 is 10 seconds, considering traffic signals.

Thus, by combining BFS to track paths and managing time at signals, we've efficiently solved the problem.

Solution Implementation

1from collections import defaultdict, deque
2from math import inf
3from typing import List
4
5class Solution:
6    def secondMinimum(self, n: int, edges: List[List[int]], 
7                      travel_time: int, light_change: int) -> int:
8        # Create a graph as an adjacency list
9        graph = defaultdict(set)
10        # Populate the graph with bidirectional edges
11        for start, end in edges:
12            graph[start].add(end)
13            graph[end].add(start)
14      
15        # Queue for performing BFS, starting with node 1, and elapsed time is 0
16        queue = deque([(1, 0)])
17        # Initialize distances array, store the shortest and second shortest distances
18        distances = [[inf] * 2 for _ in range(n + 1)]
19        distances[1][0] = 0  # Distance from node 1 to itself is 0
20      
21        # Perform BFS to find the shortest and second shortest paths to all nodes
22        while queue:
23            current_node, elapsed_dist = queue.popleft()  # Current node and elapsed distance so far
24            for neighbor in graph[current_node]:
25                # If the new distance is less than the shortest known distance
26                if elapsed_dist + 1 < distances[neighbor][0]:
27                    distances[neighbor][0] = elapsed_dist + 1
28                    queue.append((neighbor, elapsed_dist + 1))
29                # If the new distance is between the shortest and second shortest known distances
30                elif distances[neighbor][0] < elapsed_dist + 1 < distances[neighbor][1]:
31                    distances[neighbor][1] = elapsed_dist + 1
32                    # You only need to find the second shortest path to node 'n'
33                    if neighbor == n:
34                        break
35                    queue.append((neighbor, elapsed_dist + 1))
36      
37        # Calculate the second minimum travel time based on the shortest paths
38        total_time = 0
39        for i in range(distances[n][1]):
40            total_time += travel_time
41            # If traffic light will be red before reaching the next node, wait until it turns green
42            if i < distances[n][1] - 1 and (total_time // light_change) % 2 == 1:
43                total_time = (total_time + light_change - 1) // light_change * light_change
44      
45        return total_time
46
1class Solution {
2    public int secondMinimum(int n, int[][] edges, int time, int change) {
3        // Create adjacency lists for all nodes
4        List<Integer>[] graph = new List[n + 1];
5        Arrays.setAll(graph, k -> new ArrayList<>());
6        for (int[] edge : edges) {
7            int u = edge[0], v = edge[1];
8            graph[u].add(v);
9            graph[v].add(u);
10        }
11
12        // Queue for BFS
13        Deque<int[]> queue = new LinkedList<>();
14        queue.offerLast(new int[] {1, 0}); // Start from node 1 with distance 0
15
16        // Initialize distances (two distances per node to store the two smallest distances)
17        int[][] distances = new int[n + 1][2];
18        for (int i = 0; i <= n; i++) {
19            Arrays.fill(distances[i], Integer.MAX_VALUE);
20        }
21        distances[1][0] = 0; // Distance to the starting node is zero
22
23        // Perform BFS
24        while (!queue.isEmpty()) {
25            int[] nodeData = queue.pollFirst();
26            int current = nodeData[0], distance = nodeData[1];
27
28            // Explore neighbors
29            for (int neighbor : graph[current]) {
30                // Record smallest distance
31                if (distance + 1 < distances[neighbor][0]) {
32                    distances[neighbor][0] = distance + 1;
33                    queue.offerLast(new int[] {neighbor, distance + 1});
34                } 
35                // Record second smallest distance
36                else if (distances[neighbor][0] < distance + 1 && distance + 1 < distances[neighbor][1]) {
37                    distances[neighbor][1] = distance + 1;
38                    // Early break if we reach the destination node
39                    if (neighbor == n) {
40                        break;
41                    }
42                    queue.offerLast(new int[] {neighbor, distance + 1});
43                }
44            }
45        }
46
47        // Calculate the total time to reach the destination node using the second smallest distance
48        int totalTime = 0;
49        for (int i = 0; i < distances[n][1]; ++i) {
50            totalTime += time;
51            // Adjust total time based on traffic signal change interval
52            if (i < distances[n][1] - 1 && (totalTime / change) % 2 == 1) {
53                totalTime = (totalTime + change) / change * change;
54            }
55        }
56        return totalTime;
57    }
58}
59
1#include <vector>
2#include <queue>
3#include <climits>  // For INT_MAX
4
5using namespace std;
6
7class Solution {
8public:
9    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
10        // Create adjacency lists for all nodes
11        vector<vector<int>> graph(n + 1);
12        for (const vector<int>& edge : edges) {
13            int u = edge[0];
14            int v = edge[1];
15            graph[u].push_back(v);
16            graph[v].push_back(u);
17        }
18
19        // Queue for breadth-first search (BFS)
20        queue<pair<int, int>> bfsQueue;
21        bfsQueue.push({1, 0}); // Start from node 1 with distance 0
22
23        // Initialize distances with two slots per node to store the two smallest distances
24        vector<vector<int>> distances(n + 1, vector<int>(2, INT_MAX));
25        distances[1][0] = 0; // Distance to the starting node is zero
26
27        // Perform BFS
28        while (!bfsQueue.empty()) {
29            pair<int, int> nodeData = bfsQueue.front();
30            bfsQueue.pop();
31            int currentNode = nodeData.first;
32            int currentDistance = nodeData.second;
33
34            // Explore neighbors
35            for (int neighbor : graph[currentNode]) {
36                // Record smallest distance
37                if (currentDistance + 1 < distances[neighbor][0]) {
38                    distances[neighbor][1] = distances[neighbor][0]; // Update second smallest
39                    distances[neighbor][0] = currentDistance + 1;    // Update smallest
40                    bfsQueue.push({neighbor, currentDistance + 1});
41                }
42                // Record second smallest distance
43                else if (distances[neighbor][0] < currentDistance + 1 &&
44                        currentDistance + 1 < distances[neighbor][1]) {
45                    distances[neighbor][1] = currentDistance + 1;
46                    // No early break needed as we need to explore all paths thoroughly
47                    bfsQueue.push({neighbor, currentDistance + 1});
48                }
49            }
50        }
51
52        // Calculate the total time to reach the destination node using the second smallest distance
53        int totalTime = 0;
54        for (int i = 0; i < distances[n][1]; ++i) {
55            totalTime += time;
56            // Adjust total time based on traffic signal change interval
57            if (i < distances[n][1] - 1 && (totalTime / change) % 2 == 1) {
58                totalTime += change - (totalTime % change);  // Wait for the green signal
59            }
60        }
61        return totalTime;
62    }
63};
64
1// Initialize adjacency list for each node
2const adjacencyLists: number[][] = [];
3
4// Initialize distances (two distances per node to store the two smallest distances)
5const distances: number[][] = [];
6
7// Initialize the queue for BFS
8const queue: number[][] = [];
9
10function secondMinimum(n: number, edges: number[][], time: number, change: number): number {
11    // Construct the adjacency lists from the edges
12    for(let i = 1; i <= n; i++){
13        adjacencyLists[i] = [];
14    }
15
16    edges.forEach(([u, v]) => {
17        adjacencyLists[u].push(v);
18        adjacencyLists[v].push(u);
19    });
20
21    // Initialize distances array with infinite distance values
22    for (let i = 1; i <= n; i++) {
23        distances[i] = [Number.MAX_VALUE, Number.MAX_VALUE];
24    }
25    distances[1][0] = 0; // Distance to starting node is zero
26
27    // Start BFS by adding the first node to the queue
28    queue.push([1, 0]); // Node 1, distance 0
29
30    while(queue.length > 0) {
31        const [currentNode, currentDistance] = queue.shift()!; // Take first element from queue
32
33        // Explore neighbors of the current node
34        adjacencyLists[currentNode].forEach(neighbor => {
35            // Update the distance if a smaller one is found
36            if (currentDistance + 1 < distances[neighbor][0]) {
37                distances[neighbor][0] = currentDistance + 1;
38                queue.push([neighbor, currentDistance + 1]);
39            }
40            // Record the second smallest distance if applicable
41            else if (distances[neighbor][0] < currentDistance + 1 && currentDistance + 1 < distances[neighbor][1]) {
42                distances[neighbor][1] = currentDistance + 1;
43                queue.push([neighbor, currentDistance + 1]);
44            }
45        });
46    }
47
48    // Calculate total time taken to reach destination with the second smallest distance
49    let totalTime = 0;
50    for (let i = 0; i < distances[n][1]; i++) {
51        totalTime += time;
52
53        // Check if we need to wait for the traffic signal to change
54        if (i < distances[n][1] - 1 && totalTime % (2 * change) >= change) {
55            totalTime += 2 * change - (totalTime % change) - change;
56        }
57    }
58
59    return totalTime; // Return the total time to reach the destination
60}
61
Not Sure What to Study? Take the 2-min Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Time and Space Complexity

The time complexity of the given code is O(n * m) where n is the number of nodes in the graph and m is the number of edges. Each node gets processed at most twice (once for each of its two shortest paths since we're looking for the second minimum time). For each node, we explore all its adjacent edges. In the worst case, the total number of operations can be proportional to n times m.

The space complexity is O(n). The extra space is used for:

  1. The adjacency list g which, in the worst case, could hold all nodes and edges, so O(n + m), but since m is at most n(n-1)/2, it simplifies to O(n).
  2. The queue q which could, in the worst case, contain all nodes. The queue holds nodes with their distance which is O(n).
  3. The dist array which contains two entries for each node, so 2n which simplifies to O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫