3112. Minimum Time to Visit Disappearing Nodes LeetCode Solution
In this guide, you will get 3112. Minimum Time to Visit Disappearing Nodes LeetCode Solution with the best time and space complexity. The solution to Minimum Time to Visit Disappearing Nodes 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 Minimum Time to Visit Disappearing Nodes
There is an undirected graph of n nodes. You are given a 2D array edges, where edges[i] = [ui, vi, lengthi] describes an edge between node ui and node vi with a traversal time of lengthi units.
Additionally, you are given an array disappear, where disappear[i] denotes the time when the node i disappears from the graph and you won’t be able to visit it.
Note that the graph might be disconnected and might contain multiple edges.
Return the array answer, with answer[i] denoting the minimum units of time required to reach node i from node 0. If node i is unreachable from node 0 then answer[i] is -1.
For node 0, we don’t need any time as it is our starting point.
For node 1, we need at least 2 units of time to traverse edges[0]. Unfortunately, it disappears at that moment, so we won’t be able to visit it.
For node 2, we need at least 4 units of time to traverse edges[2].
We are starting our journey from node 0, and our goal is to find the minimum time required to reach each node before it disappears.
For node 0, we don’t need any time as it is the starting point.
For node 1, we need at least 2 units of time to traverse edges[0].
For node 2, we need at least 3 units of time to traverse edges[0] and edges[1].
Example 3:
Input: n = 2, edges = [[0,1,1]], disappear = [1,1]
Output: [0,-1]
Explanation:
Exactly when we reach node 1, it disappears.
Constraints:
1 <= n <= 5 * 104
0 <= edges.length <= 105
edges[i] == [ui, vi, lengthi]
0 <= ui, vi <= n – 1
1 <= lengthi <= 105
disappear.length == n
1 <= disappear[i] <= 105
Complexity Analysis
Time Complexity: O((|V| + |E|)\log |V|)
Space Complexity: O(|E| + |V|)
3112. Minimum Time to Visit Disappearing Nodes LeetCode Solution in C++
class Solution {
public:
vector<int> minimumTime(int n, vector<vector<int>>& edges,
vector<int>& disappear) {
vector<vector<pair<int, int>>> graph(n);
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
const int w = edge[2];
graph[u].emplace_back(v, w);
graph[v].emplace_back(u, w);
}
return dijkstra(graph, 0, disappear);
}
private:
vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int src,
const vector<int>& disappear) {
vector<int> dist(graph.size(), INT_MAX);
dist[src] = 0;
using P = pair<int, int>; // (d, u)
priority_queue<P, vector<P>, greater<>> minHeap;
minHeap.emplace(dist[src], src);
while (!minHeap.empty()) {
const auto [d, u] = minHeap.top();
minHeap.pop();
if (d > dist[u])
continue;
for (const auto& [v, w] : graph[u])
if (d + w < disappear[v] && d + w < dist[v]) {
dist[v] = d + w;
minHeap.push({dist[v], v});
}
}
for (int& d : dist)
if (d == INT_MAX)
d = -1;
return dist;
}
}; /* code provided by PROGIEZ */
3112. Minimum Time to Visit Disappearing Nodes LeetCode Solution in Java
class Solution {
public int[] minimumTime(int n, int[][] edges, int[] disappear) {
List<Pair<Integer, Integer>>[] graph = new List[n];
for (int i = 0; i < n; i++)
graph[i] = new ArrayList<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
final int w = edge[2];
graph[u].add(new Pair<>(v, w));
graph[v].add(new Pair<>(u, w));
}
return dijkstra(graph, 0, disappear);
}
private int[] dijkstra(List<Pair<Integer, Integer>>[] graph, int src, int[] disappear) {
int[] dist = new int[graph.length];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
Queue<Pair<Integer, Integer>> minHeap =
new PriorityQueue<>(Comparator.comparing(Pair::getKey)) {
{ offer(new Pair<>(dist[src], src)); } // (d, u)
};
while (!minHeap.isEmpty()) {
final int d = minHeap.peek().getKey();
final int u = minHeap.poll().getValue();
if (d > dist[u])
continue;
for (Pair<Integer, Integer> pair : graph[u]) {
final int v = pair.getKey();
final int w = pair.getValue();
if (d + w < disappear[v] && d + w < dist[v]) {
dist[v] = d + w;
minHeap.offer(new Pair<>(dist[v], v));
}
}
}
for (int i = 0; i < dist.length; ++i)
if (dist[i] == Integer.MAX_VALUE)
dist[i] = -1;
return dist;
}
} // code provided by PROGIEZ
3112. Minimum Time to Visit Disappearing Nodes LeetCode Solution in Python
class Solution:
def minimumTime(
self,
n: int,
edges: list[list[int]],
disappear: list[int],
) -> list[int]:
graph = [[] for _ in range(n)]
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
return self._dijkstra(graph, 0, disappear)
def _dijkstra(
self,
graph: list[list[tuple[int, int]]],
src: int,
disappear: list[int],
) -> list[int]:
dist = [math.inf] * len(graph)
dist[src] = 0
minHeap = [(dist[src], src)] # (d, u)
while minHeap:
d, u = heapq.heappop(minHeap)
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < disappear[v] and d + w < dist[v]:
dist[v] = d + w
heapq.heappush(minHeap, (dist[v], v))
return [d if d != math.inf else -1
for d in dist] # code by PROGIEZ
