LeetCode 2045: Second Minimum Time to Reach Destination Solution
Master LeetCode problem 2045 (Second Minimum Time to Reach Destination), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
2045. Second Minimum Time to Reach Destination
Problem Explanation
Explanation
To solve this problem, we can model the situation as a graph traversal problem where we need to find the second minimum time to reach the destination vertex n starting from vertex 1. We can use Dijkstra's algorithm to find the shortest paths from vertex 1 to all other vertices in the graph.
We need to consider the effect of the traffic signals while traversing the graph. We can maintain two distances for each vertex: one for the current time and one for the time when the signal changes. This way, we can consider the waiting time at each vertex when the signal is red.
The algorithm involves iterating through the vertices and edges while considering the time taken to reach each vertex, waiting time at each vertex, and the time to change the signal.
The time complexity of this algorithm is O(NlogN) where N is the number of vertices in the graph. The space complexity is O(N).
Solution Code
class Solution {
public int secondMinimum(int n, int[][] edges, int time, int change) {
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int[] edge : edges) {
graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(new int[]{edge[1], time});
graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(new int[]{edge[0], time});
}
int[][] dist = new int[n + 1][change + 1];
for (int[] d : dist) {
Arrays.fill(d, Integer.MAX_VALUE);
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, 1, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int curTime = cur[0];
int curVertex = cur[1];
int curChange = cur[2];
if (curVertex == n) {
return curTime;
}
if (curTime >= dist[curVertex][curChange]) {
continue;
}
dist[curVertex][curChange] = curTime;
int nextChange = (curChange + 1) % (2 * change);
int waitTime = 0;
if (nextChange >= change) {
waitTime = change - (nextChange - change);
}
for (int[] neighbor : graph.getOrDefault(curVertex, new ArrayList<>())) {
int neighborVertex = neighbor[0];
int neighborTime = neighbor[1];
int newTime = curTime + neighborTime + waitTime;
if (newTime < dist[neighborVertex][nextChange]) {
pq.offer(new int[]{newTime, neighborVertex, nextChange});
}
}
}
return -1;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 2045 (Second Minimum Time to Reach Destination)?
This page provides optimized solutions for LeetCode problem 2045 (Second Minimum Time to Reach Destination) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 2045 (Second Minimum Time to Reach Destination)?
The time complexity for LeetCode 2045 (Second Minimum Time to Reach Destination) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 2045 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2045 in Java, C++, or Python.