2045. Second Minimum Time to Reach Destination LeetCode Solution
In this guide, you will get 2045. Second Minimum Time to Reach Destination LeetCode Solution with the best time and space complexity. The solution to Second Minimum Time to Reach Destination problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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
Complexity Analysis
Time Complexity: O(|V| + |E|), where |V| = n and |E| = |\texttt{edges}|
Space Complexity: O(|V| + |E|), where |V| = n and |E| = |\texttt{edges}|
2045. Second Minimum Time to Reach Destination LeetCode Solution in C++
class Solution {
public:
int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
vector<vector<int>> graph(n + 1);
queue<pair<int, int>> q{{{1, 0}}};
// minTime[u][0] := the first minimum time to reach the node u
// minTime[u][1] := the second minimum time to reach the node u
vector<vector<int>> minTime(n + 1, vector<int>(2, INT_MAX));
minTime[1][0] = 0;
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
graph[u].push_back(v);
graph[v].push_back(u);
}
while (!q.empty()) {
const auto [u, prevTime] = q.front();
q.pop();
// Start from green.
// If `numChangeSignal` is odd, now red.
// If `numChangeSignal` is even, now green.
const int numChangeSignal = prevTime / change;
const int waitTime =
numChangeSignal % 2 == 0 ? 0 : change - prevTime % change;
const int newTime = prevTime + waitTime + time;
for (const int v : graph[u])
if (newTime < minTime[v][0]) {
minTime[v][0] = newTime;
q.emplace(v, newTime);
} else if (minTime[v][0] < newTime && newTime < minTime[v][1]) {
if (v == n)
return newTime;
minTime[v][1] = newTime;
q.emplace(v, newTime);
}
}
throw;
}
}; /* code provided by PROGIEZ */
2045. Second Minimum Time to Reach Destination LeetCode Solution in Java
class Solution {
public int secondMinimum(int n, int[][] edges, int time, int change) {
List<Integer>[] graph = new List[n + 1];
// (index, time)
Queue<Pair<Integer, Integer>> q = new ArrayDeque<>(List.of(new Pair<>(1, 0)));
// minTime[u][0] := the first minimum time to reach the node u
// minTime[u][1] := the second minimum time to reach the node u
int[][] minTime = new int[n + 1][2];
Arrays.stream(minTime).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
minTime[1][0] = 0;
for (int i = 1; i <= n; ++i)
graph[i] = new ArrayList<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
graph[u].add(v);
graph[v].add(u);
}
while (!q.isEmpty()) {
final int u = q.peek().getKey();
final int prevTime = q.poll().getValue();
// Start from green.
// If `numChangeSignal` is odd, now red.
// If `numChangeSignal` is even, now green.
final int numChangeSignal = prevTime / change;
final int waitTime = numChangeSignal % 2 == 0 ? 0 : change - prevTime % change;
final int newTime = prevTime + waitTime + time;
for (final int v : graph[u])
if (newTime < minTime[v][0]) {
minTime[v][0] = newTime;
q.offer(new Pair<>(v, newTime));
} else if (minTime[v][0] < newTime && newTime < minTime[v][1]) {
if (v == n)
return newTime;
minTime[v][1] = newTime;
q.offer(new Pair<>(v, newTime));
}
}
throw new IllegalArgumentException();
}
} // code provided by PROGIEZ
2045. Second Minimum Time to Reach Destination LeetCode Solution in Python
class Solution:
def secondMinimum(
self,
n: int,
edges: list[list[int]],
time: int,
change: int,
) -> int:
graph = [[] for _ in range(n + 1)]
q = collections.deque([(1, 0)])
# minTime[u][0] := the first minimum time to reach the node u
# minTime[u][1] := the second minimum time to reach the node u
minTime = [[math.inf] * 2 for _ in range(n + 1)]
minTime[1][0] = 0
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
while q:
u, prevTime = q.popleft()
# Start from green.
# If `numChangeSignal` is odd, now red.
# If numChangeSignal is even -> now gree
numChangeSignal = prevTime // change
waitTime = (0 if numChangeSignal % 2 == 0
else change - (prevTime % change))
newTime = prevTime + waitTime + time
for v in graph[u]:
if newTime < minTime[v][0]:
minTime[v][0] = newTime
q.append((v, newTime))
elif minTime[v][0] < newTime < minTime[v][1]:
if v == n:
return newTime
minTime[v][1] = newTime
q.append((v, newTime)) # code by PROGIEZ
