Minimum Time to Visit Disappearing Nodes
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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.
Examples
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]` 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 * 10^40 <= edges.length <= 10^5edges[i] == [ui, vi, lengthi]0 <= ui, vi <= n - 11 <= lengthi <= 10^5disappear.length == n1 <= disappear[i] <= 10^5
Solution
Method 1 – Dijkstra's Algorithm with Disappear Constraints
Intuition
We need to find the shortest time to each node, but can only visit a node before its disappear time. This is a classic shortest path problem with an extra constraint, so we use Dijkstra's algorithm and skip nodes that disappear before we arrive.
Approach
- Build the undirected graph from the edges.
- Use a min-heap to process nodes by earliest arrival time.
- For each node, if arrival time is less than disappear time, update answer and continue to neighbors.
- If a node is unreachable or disappears before arrival, answer is -1.
- Return the answer array.
Code
C++
#include <queue>
class Solution {
public:
vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
vector<vector<pair<int,int>>> g(n);
for (auto& e : edges) {
g[e[0]].emplace_back(e[1], e[2]);
g[e[1]].emplace_back(e[0], e[2]);
}
vector<int> ans(n, -1);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.emplace(0, 0);
while (!pq.empty()) {
auto [t, u] = pq.top(); pq.pop();
if (ans[u] != -1) continue;
if (t >= disappear[u]) continue;
ans[u] = t;
for (auto& [v, w] : g[u]) {
if (ans[v] == -1) pq.emplace(t + w, v);
}
}
return ans;
}
};
Go
func MinimumTime(n int, edges [][]int, disappear []int) []int {
g := make([][][2]int, n)
for _, e := range edges {
g[e[0]] = append(g[e[0]], [2]int{e[1], e[2]})
g[e[1]] = append(g[e[1]], [2]int{e[0], e[2]})
}
ans := make([]int, n)
for i := range ans { ans[i] = -1 }
pq := &heapPair{}
heap.Init(pq)
heap.Push(pq, pair{0, 0})
for pq.Len() > 0 {
p := heap.Pop(pq).(pair)
if ans[p.u] != -1 || p.d >= disappear[p.u] { continue }
ans[p.u] = p.d
for _, e := range g[p.u] {
v, w := e[0], e[1]
if ans[v] == -1 {
heap.Push(pq, pair{p.d + w, v})
}
}
}
return ans
}
type pair struct{ d, u int }
type heapPair []pair
func (h heapPair) Len() int { return len(h) }
func (h heapPair) Less(i, j int) bool { return h[i].d < h[j].d }
func (h heapPair) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *heapPair) Push(x interface{}) { *h = append(*h, x.(pair)) }
func (h *heapPair) Pop() interface{} { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
Java
class Solution {
public int[] minimumTime(int n, int[][] edges, int[] disappear) {
List<int[]>[] g = new List[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int[] e : edges) {
g[e[0]].add(new int[]{e[1], e[2]});
g[e[1]].add(new int[]{e[0], e[2]});
}
int[] ans = new int[n];
Arrays.fill(ans, -1);
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int t = cur[0], u = cur[1];
if (ans[u] != -1 || t >= disappear[u]) continue;
ans[u] = t;
for (int[] e : g[u]) {
int v = e[0], w = e[1];
if (ans[v] == -1) pq.offer(new int[]{t + w, v});
}
}
return ans;
}
}
Kotlin
class Solution {
fun minimumTime(n: Int, edges: Array<IntArray>, disappear: IntArray): IntArray {
val g = Array(n) { mutableListOf<Pair<Int, Int>>() }
for (e in edges) {
g[e[0]].add(e[1] to e[2])
g[e[1]].add(e[0] to e[2])
}
val ans = IntArray(n) { -1 }
val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
pq.add(0 to 0)
while (pq.isNotEmpty()) {
val (t, u) = pq.poll()
if (ans[u] != -1 || t >= disappear[u]) continue
ans[u] = t
for ((v, w) in g[u]) {
if (ans[v] == -1) pq.add(t + w to v)
}
}
return ans
}
}
Python
from typing import List
import heapq
class Solution:
def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
g = [[] for _ in range(n)]
for u, v, w in edges:
g[u].append((v, w))
g[v].append((u, w))
ans = [-1] * n
heap = [(0, 0)]
while heap:
t, u = heapq.heappop(heap)
if ans[u] != -1 or t >= disappear[u]:
continue
ans[u] = t
for v, w in g[u]:
if ans[v] == -1:
heapq.heappush(heap, (t + w, v))
return ans
Rust
use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
pub fn minimum_time(n: i32, edges: Vec<Vec<i32>>, disappear: Vec<i32>) -> Vec<i32> {
let n = n as usize;
let mut g = vec![vec![]; n];
for e in &edges {
g[e[0] as usize].push((e[1] as usize, e[2]));
g[e[1] as usize].push((e[0] as usize, e[2]));
}
let mut ans = vec![-1; n];
let mut heap = BinaryHeap::new();
heap.push(Reverse((0, 0)));
while let Some(Reverse((t, u))) = heap.pop() {
if ans[u] != -1 || t >= disappear[u] { continue; }
ans[u] = t;
for &(v, w) in &g[u] {
if ans[v] == -1 {
heap.push(Reverse((t + w, v)));
}
}
}
ans
}
}
TypeScript
class Solution {
minimumTime(n: number, edges: number[][], disappear: number[]): number[] {
const g: number[][][] = Array.from({length: n}, () => []);
for (const [u, v, w] of edges) {
g[u].push([v, w]);
g[v].push([u, w]);
}
const ans = Array(n).fill(-1);
const heap: [number, number][] = [[0, 0]];
while (heap.length) {
heap.sort((a, b) => a[0] - b[0]);
const [t, u] = heap.shift()!;
if (ans[u] !== -1 || t >= disappear[u]) continue;
ans[u] = t;
for (const [v, w] of g[u]) {
if (ans[v] === -1) heap.push([t + w, v]);
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O((n + m) log n)— Dijkstra's algorithm with a heap for all nodes and edges. - 🧺 Space complexity:
O(n + m)— For graph storage and heap.