2045. Second Minimum Time to Reach Destination

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.

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

Approach 01

#include <vector>
#include <queue>
#include <climits>

using namespace std;

class Solution {
public:
    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
        vector<vector<int>> adjacencyList(n + 1);
        queue<pair<int, int>> bfsQueue{{{1, 0}}};

        // minTime[node][0] := the first minimum time to reach the node
        // minTime[node][1] := the second minimum time to reach the node
        vector<vector<int>> minTime(n + 1, vector<int>(2, INT_MAX));
        minTime[1][0] = 0;

        // Build the adjacency list for the graph
        for (const vector<int>& edge : edges) {
            const int u = edge[0];
            const int v = edge[1];
            adjacencyList[u].push_back(v);
            adjacencyList[v].push_back(u);
        }

        // Perform BFS to find the second minimum time to reach node n
        while (!bfsQueue.empty()) {
            const auto [currentNode, prevTime] = bfsQueue.front();
            bfsQueue.pop();

            // Calculate the wait time based on the traffic light signal
            const int numChangeSignal = prevTime / change;
            const int waitTime = (numChangeSignal % 2 == 0) ? 0 : change - prevTime % change;
            const int newTime = prevTime + waitTime + time;

            // Traverse the neighbors of the current node
            for (const int neighbor : adjacencyList[currentNode]) {
                // Update the minimum time to reach the neighbor
                if (newTime < minTime[neighbor][0]) {
                    minTime[neighbor][0] = newTime;
                    bfsQueue.emplace(neighbor, newTime);
                }
                // Update the second minimum time to reach the neighbor
                else if (minTime[neighbor][0] < newTime && newTime < minTime[neighbor][1]) {
                    if (neighbor == n)
                        return newTime;
                    minTime[neighbor][1] = newTime;
                    bfsQueue.emplace(neighbor, newTime);
                }
            }
        }

        throw;
    }
};

from collections import deque
import sys

class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        adjacencyList = [[] for _ in range(n + 1)]
        bfsQueue = deque([(1, 0)])

        # minTime[node][0] := the first minimum time to reach the node
        # minTime[node][1] := the second minimum time to reach the node
        minTime = [[sys.maxsize, sys.maxsize] for _ in range(n + 1)]
        minTime[1][0] = 0

        # Build the adjacency list for the graph
        for edge in edges:
            u = edge[0]
            v = edge[1]
            adjacencyList[u].append(v)
            adjacencyList[v].append(u)

        # Perform BFS to find the second minimum time to reach node n
        while bfsQueue:
            currentNode, prevTime = bfsQueue.popleft()

            # Calculate the wait time based on the traffic light signal
            numChangeSignal = prevTime // change
            waitTime = 0 if numChangeSignal % 2 == 0 else change - prevTime % change
            newTime = prevTime + waitTime + time

            # Traverse the neighbors of the current node
            for neighbor in adjacencyList[currentNode]:
                # Update the minimum time to reach the neighbor
                if newTime < minTime[neighbor][0]:
                    minTime[neighbor][0] = newTime
                    bfsQueue.append((neighbor, newTime))
                # Update the second minimum time to reach the neighbor
                elif minTime[neighbor][0] < newTime < minTime[neighbor][1]:
                    if neighbor == n:
                        return newTime
                    minTime[neighbor][1] = newTime
                    bfsQueue.append((neighbor, newTime))

Time Complexity

• Building the Adjacency List:

  Constructing the adjacency list requires iterating over all the edges, which takes \( O(E) \) time, where E is the number of edges.

• BFS Traversal:

  The BFS traversal involves visiting each node and its neighbors. In the worst case, each node and its edges are processed twice, once for the first minimum time and once for the second minimum time. Thus, this step takes \( O(V + E) \) time, where V is the number of nodes.

• Overall Time Complexity:

  The overall time complexity is \( O(V + E) \), dominated by the BFS traversal.

Space Complexity

• Adjacency List:

  The adjacency list stores all edges, requiring \( O(V + E) \) space.

• BFS Queue:

  In the worst case, the queue can hold all nodes, leading to \( O(V) \) space.

• Minimum Time Array:

  The minTime array stores two times for each node, resulting in \( O(2V) = O(V) space.

• Overall Space Complexity:

  The overall space complexity is \( O(V + E) \), dominated by the adjacency list.