Minimum Time to Visit Disappearing Nodes
Source: leetcode
Difficulty: Medium
Tags: array, graph, heap-priority-queue, shortest-path

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:**


![](https://assets.leetcode.com/uploads/2024/08/11/output-onlinepngtools.png)


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:**


![](https://assets.leetcode.com/uploads/2024/08/11/output-onlinepngtools-1.png)


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`




C++ solution:
class Solution {
public:
    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
        vector<vector<pair<int,int>>>adj(n);
        for(int i=0;i<edges.size();i++){
            int u=edges[i][0];
            int v=edges[i][1];
            int wt=edges[i][2];
            adj[u].push_back({v,wt});
            adj[v].push_back({u,wt});
        }
        queue<pair<int,int>>q;
        q.push({0,0});
        vector<int>dist(n,1e9);
        dist[0]=0;
        while(!q.empty()){
            int node=q.front().first;
            int distance=q.front().second;
            q.pop();
            if(distance>dist[node]) continue;
            for(auto it:adj[node]){
                int adjnode=it.first;
                int wt=it.second;
                if(dist[adjnode]>distance+wt && distance+wt<disappear[adjnode]){
                    dist[adjnode]=distance+wt;
                    q.push({adjnode,distance+wt});
                }
            }
        }
        for(int i=0;i<n;i++){
            if(dist[i]==1e9)
            dist[i]=-1;
        }
        return dist;
    }
};

Go solution:
type Pair struct {
	time int
	node int
}

type MinHeap []Pair

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i].time < h[j].time }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Pair)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func minimumTime(n int, edges [][]int, disappear []int) []int {
	ans := make([]int, n)
	for i := range ans {
		ans[i] = -1
	}
	ans[0] = 0

	tree := make([][]Pair, n)
	for _, edge := range edges {
		u, v, l := edge[0], edge[1], edge[2]
		tree[u] = append(tree[u], Pair{l, v})
		tree[v] = append(tree[v], Pair{l, u})
	}

	h := make(MinHeap, len(tree[0]))
	copy(h, tree[0])
	heap.Init(&h)

	for len(h) > 0 {
		p := heap.Pop(&h).(Pair)
		l, u := p.time, p.node
		if disappear[u] <= l || ans[u] != -1 {
			continue
		}
		ans[u] = l
		for _, nv := range tree[u] {
			heap.Push(&h, Pair{l + nv.time, nv.node})
		}
	}

	return ans
}

Java solution:
class Solution {
    public int[] minimumTime(int n, int[][] edges, int[] disappear) {
        Map<Integer, List<int[]>> map = new HashMap<>();
        for(int[] edge: edges){
            int u = edge[0];
            int v = edge[1];
            int len = edge[2];
            map.putIfAbsent(u, new ArrayList<>());
            map.putIfAbsent(v, new ArrayList<>());
            map.get(u).add(new int[]{v, len});
            map.get(v).add(new int[]{u, len});
        }
        
        
        int[] res = new int[n];
        Arrays.fill(res, -1);
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(a->a[1]));
        pq.offer(new int[]{0, 0});
        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            int node = cur[0];
            int time = cur[1];
            if(res[node] != -1){
                continue;
            }
            res[node] = time;
            
            if(map.containsKey(node)){
                for(int[] no:map.get(node)){
                    int new_node = no[0];
                    int new_time = no[1];
                    if(res[new_node]==-1 && time+new_time < disappear[new_node]){
                        pq.offer(new int[]{new_node, time+new_time});
                    }
                }
            }
        }
        return res;
    }
}

JavaScript solution:
function minimumTime(n, edges, disappear) {
    const graph = {}; 
    for (let i = 0; i < n; i++) {
        graph[i] = [];
    }
    for (const [u, v, length] of edges) {
        graph[u].push({ node: v, length });
        graph[v].push({ node: u, length });
    }

    const answer = new Array(n).fill(-1);
    const pq = new MinHeap();
    const visited = new Set(); 

    pq.insert(0, 0); 

    while (!pq.isEmpty()) {
        const [node, distance] = pq.removeMin();

        if (visited.has(node)) continue; 
        visited.add(node);

        answer[node] = distance; 

        for (const { node: adjNode, length } of graph[node]) {
            if (disappear[adjNode] > distance + length && !visited.has(adjNode)) {
                pq.insert(adjNode, distance + length);
            }
        }
    }

    return answer;
}

// Basic MinHeap implementation 
class MinHeap {
    constructor() {
        this.heap = []; 
    }

    insert(node, distance) {
        this.heap.push([node, distance]);
        this.heapifyUp(); 
    }

    removeMin() {
        [this.heap[0], this.heap[this.heap.length - 1]] = [this.heap[this.heap.length - 1], this.heap[0]]; 
        const min = this.heap.pop();
        this.heapifyDown();
        return min;
    }

    heapifyUp() {
        let index = this.heap.length - 1;
        while (this.hasParent(index) && this.parent(index)[1] > this.heap[index][1]) {
            [this.heap[this.parentIndex(index)], this.heap[index]] = [this.heap[index], this.heap[this.parentIndex(index)]];
            index = this.parentIndex(index);
        }
    }

    heapifyDown() {
        let index = 0;
        while (this.hasLeftChild(index)) {
            let smallerChildIndex = this.leftChildIndex(index);
            if (this.hasRightChild(index) && this.rightChild(index)[1] < this.leftChild(index)[1]) {
                smallerChildIndex = this.rightChildIndex(index);
            }

            if (this.heap[index][1] < this.heap[smallerChildIndex][1]) {
                break;
            } else {
                [this.heap[index], this.heap[smallerChildIndex]] = [this.heap[smallerChildIndex], this.heap[index]];
            }
            index = smallerChildIndex;
        }
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    parentIndex(index) {
        return Math.floor((index - 1) / 2);
    }

    leftChildIndex(index) {
        return 2 * index + 1;
    }

    rightChildIndex(index) {
        return 2 * index + 2;
    }

    hasParent(index) {
        return this.parentIndex(index) >= 0;
    }

    hasLeftChild(index) {
        return this.leftChildIndex(index) < this.heap.length;
    }

    hasRightChild(index) {
        return this.rightChildIndex(index) < this.heap.length;
    }

    parent(index) {
        return this.heap[this.parentIndex(index)];
    }

    leftChild(index) {
        return this.heap[this.leftChildIndex(index)];
    }

    rightChild(index) {
        return this.heap[this.rightChildIndex(index)];
    }
}

Python solution:
class Solution:
    def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
        adj = defaultdict(list)
        for v1,v2,weight in edges:
            adj[v1].append((weight,v2))
            adj[v2].append((weight,v1))
        
        res = [float('inf')]*n
        q = deque([(0,0)])
        while q:
            time, node = q.popleft()
            if time > res[node]: continue
            res[node] = time
            for wei,nxt in adj[node]:
                nxt_time = time+wei
                if nxt_time < disappear[nxt] and nxt_time < res[nxt]:
                    res[nxt] = nxt_time
                    q.append((nxt_time,nxt))
            
        return [time if time != float('inf') else -1 for time in res ]

Ruby solution:
M = 1e5.to_i
V = M * 10

def minimum_time n, e, da
    r, d = [-1] * n, [M] * n
    r[0] = d[0] = 0
    g = Array.new(n) { [] }
    for x, y, l in e
        next if x == y
        g[x] << [y, l]
        g[y] << [x, l]
    end
    t = [nil] * n + [*n.times]
    for i in (1...n).reverse_each
        t[i], y = t[i * 2], t[i * 2 + 1]
        t[i] = y if d[t[i]] > d[y]
    end
    while (x = d[i = t[1]]) < V
        r[i] = x if x < da[i]
        d[j = i] = V
        j += n
        while (j /= 2) > 0
            t[j], y = t[j * 2], t[j * 2 + 1]
            t[j] = y if d[t[j]] > d[y]
        end
        next if r[i] < 0
        for j, l in g[i]
            next if d[j] == V || x + l >= d[j]
            d[j] = x + l
            j += n
            while (j /= 2) > 0
                t[j], y = t[j * 2], t[j * 2 + 1]
                t[j] = y if d[t[j]] > d[y]
            end
        end
    end
    r
end