Minimum Time to Visit Disappearing Nodes
MedPrompt
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.
Example 1:
Input: n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]
Output: [0,-1,4]
Explanation:
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 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].
Example 2:
Input: n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,3,5]
Output: [0,2,3]
Explanation:
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]andedges[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 * 1040 <= edges.length <= 105edges[i] == [ui, vi, lengthi]0 <= ui, vi <= n - 11 <= lengthi <= 105disappear.length == n1 <= disappear[i] <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a basic implementation of Dijkstra's algorithm. It finds the shortest path from the source node 0 to all other nodes. The main characteristic of this naive version is how it selects the next node to process. At each step, it performs a linear scan across all nodes to find the unvisited one with the minimum current travel time. The core logic is adapted to handle the disappearance constraint: a path to a node is only considered if the arrival time is strictly less than the node's disappearance time. While correct, this method is inefficient due to the repeated linear scans.
Algorithm
- Graph Representation: Build an adjacency list from the
edgesarray.adj[i]will store a list of pairs, where each pair consists of a neighbor node and the edge weight (time). - Initialization: Create a
minTimearray of sizeninitialized to infinity, representing the shortest time from node 0. SetminTime[0] = 0. Also, create a booleanvisitedarray of the same size, initialized tofalse. - Iterative Search: Loop
ntimes. In each iteration:- Find the unvisited node
uwith the smallestminTimevalue. This requires a linear scan through allnnodes. - If no such node is found (all remaining unvisited nodes have infinite time), it means they are unreachable, so break the loop.
- Mark node
uas visited.
- Find the unvisited node
- Edge Relaxation: For each neighbor
vof the selected nodeu:- Calculate the time to reach
vthroughu:newTime = minTime[u] + weight(u, v). - Constraint Check: This new path is only considered if it's a valid visit (
newTime < disappear[v]) and it's a shorter path (newTime < minTime[v]). - If both conditions are met, update
minTime[v] = newTime.
- Calculate the time to reach
- Finalization: After the loops complete, iterate through the
minTimearray. Any value that is still infinity means the corresponding node is unreachable. Replace these values with-1.
Walkthrough
The algorithm begins by converting the edge list into a more usable adjacency list format. It then initializes a minTime array to keep track of the shortest time to reach each node, with minTime[0] set to 0 and all others to a value representing infinity. The main part of the algorithm is a loop that runs up to n times. In each iteration, it searches for the unvisited node u that is currently closest to the source. Once u is found, it is marked as visited, and we try to "relax" its edges. For each neighbor v of u, we calculate the time it would take to reach v by passing through u. If this new time is less than disappear[v] and also less than the current minTime[v], we update minTime[v]. This process continues until all reachable nodes have been visited. Finally, any node with an infinite minTime is marked as unreachable (-1).
import java.util.*; class Solution { public int[] minimumTime(int n, int[][] edges, int[] disappear) { List<List<int[]>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int[] edge : edges) { adj.get(edge[0]).add(new int[]{edge[1], edge[2]}); adj.get(edge[1]).add(new int[]{edge[0], edge[2]}); } int[] minTime = new int[n]; Arrays.fill(minTime, Integer.MAX_VALUE); minTime[0] = 0; boolean[] visited = new boolean[n]; for (int count = 0; count < n; count++) { int u = -1; int t = Integer.MAX_VALUE; // Find the unvisited node with the smallest time for (int i = 0; i < n; i++) { if (!visited[i] && minTime[i] < t) { t = minTime[i]; u = i; } } if (u == -1) { break; // All remaining nodes are unreachable } visited[u] = true; for (int[] edge : adj.get(u)) { int v = edge[0]; int weight = edge[1]; int newTime = t + weight; if (newTime < disappear[v] && newTime < minTime[v]) { minTime[v] = newTime; } } } for (int i = 0; i < n; i++) { if (minTime[i] == Integer.MAX_VALUE) { minTime[i] = -1; } } return minTime; }}Complexity
Time
O(N^2), where N is the number of nodes. The main loop runs N times, and inside it, finding the node with the minimum distance takes O(N) time. The total time for edge relaxations across all iterations is O(E). Thus, the complexity is dominated by the node selection part, resulting in O(N^2 + E), which simplifies to O(N^2) for dense graphs.
Space
O(N + E), where N is the number of nodes and E is the number of edges. This is for storing the adjacency list (`O(N+E)`), the `minTime` array (`O(N)`), and the `visited` array (`O(N)`).
Trade-offs
Pros
Conceptually simpler than the priority queue-based version.
Easy to implement if one is not familiar with heap data structures.
Cons
The time complexity of
O(N^2)is too slow for the given constraints (Nup to 5 * 10^4), and will result in a Time Limit Exceeded error.
This approach is a highly efficient solution based on Dijkstra's algorithm, optimized with a priority queue (min-heap). It addresses the problem of finding the single-source shortest paths in a weighted graph. The priority queue ensures that we always process the node that is currently closest to the source, which is a greedy strategy that works for graphs with non-negative edge weights. The core algorithm is adapted to incorporate the disappearance constraint: a path to a node v is only considered and stored if the arrival time is strictly less than disappear[v]. This ensures that we never explore paths through nodes that would have already disappeared.
Algorithm
- Graph Representation: Construct an adjacency list where
adj[i]contains all neighbors of nodeiand the corresponding edge weights (time). - Initialization: Create a
minTimearray of sizen, initializing all values to infinity except forminTime[0], which is 0. - Priority Queue: Initialize a min-priority queue to store pairs of
(time, node). The priority queue will order elements based ontime. Insert the starting pair(0, 0). - Main Loop: While the priority queue is not empty:
- Extract the pair
(t, u)with the minimum timet. - If
tis greater thanminTime[u], this is an outdated entry from the queue (a shorter path touhas already been processed), so skip it.
- Extract the pair
- Edge Relaxation: For each neighbor
vofuwith edge weightw:- Calculate the potential new time:
newTime = t + w. - Constraint Check: If
newTime < disappear[v](path is valid) andnewTime < minTime[v](path is shorter), then:- Update
minTime[v] = newTime. - Add the new pair
(newTime, v)to the priority queue.
- Update
- Calculate the potential new time:
- Finalization: After the loop, post-process the
minTimearray. Replace any remaining infinity values with-1to indicate unreachable nodes. Return theminTimearray.
Walkthrough
First, we represent the graph using an adjacency list for quick access to neighbors. We maintain a minTime array, initialized to infinity, to store the shortest known time to reach each node from the source (node 0). minTime[0] is set to 0. A priority queue is used to efficiently retrieve the next node to visit. It stores (time, node) pairs and prioritizes the one with the smallest time.
The algorithm starts by adding (0, 0) to the queue. Then, it repeatedly extracts the node u with the minimum time t from the queue. If we've already found a better path to u, we ignore the current one. Otherwise, we explore all of u's neighbors. For each neighbor v, we calculate the arrival time newTime. If this newTime is a valid arrival (i.e., newTime < disappear[v]) and offers a shorter path than any previously found for v, we update minTime[v] and add (newTime, v) to the priority queue. This process guarantees that we find the shortest valid path to every reachable node. Finally, nodes that were never reached will have their minTime as infinity, which we convert to -1.
import java.util.*; class Solution { public int[] minimumTime(int n, int[][] edges, int[] disappear) { List<List<int[]>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int[] edge : edges) { adj.get(edge[0]).add(new int[]{edge[1], edge[2]}); adj.get(edge[1]).add(new int[]{edge[0], edge[2]}); } int[] minTime = new int[n]; Arrays.fill(minTime, Integer.MAX_VALUE); minTime[0] = 0; // PriorityQueue stores {time, node} PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); pq.offer(new int[]{0, 0}); while (!pq.isEmpty()) { int[] current = pq.poll(); int t = current[0]; int u = current[1]; // If we found a shorter path already, skip if (t > minTime[u]) { continue; } for (int[] edge : adj.get(u)) { int v = edge[0]; int weight = edge[1]; int newTime = t + weight; if (newTime < disappear[v] && newTime < minTime[v]) { minTime[v] = newTime; pq.offer(new int[]{newTime, v}); } } } for (int i = 0; i < n; i++) { if (minTime[i] == Integer.MAX_VALUE) { minTime[i] = -1; } } return minTime; }}Complexity
Time
O(E log N), where N is the number of nodes and E is the number of edges. Building the adjacency list is O(E). Each node is added to the priority queue at most once for each edge that leads to a shorter path. Each operation on the priority queue (insertion or extraction) takes O(log N) or O(log E) time. Since E can be up to N^2, log E is O(log N). The overall complexity is dominated by the priority queue operations.
Space
O(N + E), where N is the number of nodes and E is the number of edges. The adjacency list requires O(N + E) space. The `minTime` array requires O(N) space. The priority queue can, in the worst case, store an entry for each edge, leading to O(E) space.
Trade-offs
Pros
Highly efficient and optimal for this problem.
Guaranteed to find the shortest path in graphs with non-negative weights.
Passes the given time and memory constraints.
Cons
Slightly more complex to implement due to the use of a priority queue data structure.
Solutions
Solution
class Solution {public int[] minimumTime(int n, int[][] edges, int[] disappear) { List<int[]>[] g = new List[n]; Arrays.setAll(g, k->new ArrayList<>()); for (var e : edges) { int u = e[0], v = e[1], w = e[2]; g[u].add(new int[]{v, w}); g[v].add(new int[]{u, w}); } int[] dist = new int[n]; Arrays.fill(dist, 1 << 30); dist[0] = 0; PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[0] - b[0]); pq.offer(new int[]{0, 0}); while (!pq.isEmpty()) { var e = pq.poll(); int du = e[0], u = e[1]; if (du > dist[u]) { continue; } for (var nxt : g[u]) { int v = nxt[0], w = nxt[1]; if (dist[v] > dist[u] + w && dist[u] + w < disappear[v]) { dist[v] = dist[u] + w; pq.offer(new int[]{dist[v], v}); } } } int[] ans = new int[n]; for (int i = 0; i < n; ++i) { ans[i] = dist[i] < disappear[i] ? dist[i] : -1; } return ans; }}class Solution {public: vector<int> minimumTime(int n, vector<vector<int>> &edges, vector<int> &disappear) { vector<vector<pair<int, int>>> g(n); for (const auto &e : edges) { int u = e[0], v = e[1], w = e[2]; g[u].push_back({v, w}); g[v].push_back({u, w}); } vector<int> dist(n, 1 << 30); dist[0] = 0; using pii = pair<int, int>; priority_queue<pii, vector<pii>, greater<pii>> pq; pq.push({0, 0}); while (!pq.empty()) { auto [du, u] = pq.top(); pq.pop(); if (du > dist[u]) { continue; } for (auto [v, w] : g[u]) { if (dist[v] > dist[u] + w && dist[u] + w < disappear[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } vector<int> ans(n); for (int i = 0; i < n; ++i) { ans[i] = dist[i] < disappear[i] ? dist[i] : -1; } return ans; }};class Solution: def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]: g = defaultdict(list) for u, v, w in edges: g[u]. append((v, w)) g[v]. append((u, w)) dist = [inf] * n dist[0] = 0 q = [(0, 0)] while q: du, u = heappop(q) if du > dist[u]: continue for v, w in g[u]: if dist[v] > dist[u] + w and dist[u] + w < disappear[v]: dist[v] = dist[u] + w heappush(q, (dist[v], v)) return [a if a < b else - 1 for a, b in zip(dist, disappear)]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.