# Minimum Time to Visit Disappearing Nodes
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-time-to-visit-disappearing-nodes)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-to-visit-disappearing-nodes
**Algorithms:** [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Array, Heap (Priority Queue), Graph
---
## 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`.

**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.glich.co/dsa/minimum-time-to-visit-disappearing-nodes/image0.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.glich.co/dsa/minimum-time-to-visit-disappearing-nodes/image1.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`

# Approaches
## Naive Dijkstra's Algorithm
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.
**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)`).
**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 (`N` up to 5 * 10^4), and will result in a Time Limit Exceeded error.
### Explanation
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`).

```java
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;
    }
}
```
### Algorithm
- **Graph Representation**: Build an adjacency list from the `edges` array. `adj[i]` will store a list of pairs, where each pair consists of a neighbor node and the edge weight (time).
- **Initialization**: Create a `minTime` array of size `n` initialized to infinity, representing the shortest time from node 0. Set `minTime[0] = 0`. Also, create a boolean `visited` array of the same size, initialized to `false`.
- **Iterative Search**: Loop `n` times. In each iteration:
    - Find the unvisited node `u` with the smallest `minTime` value. This requires a linear scan through all `n` nodes.
    - If no such node is found (all remaining unvisited nodes have infinite time), it means they are unreachable, so break the loop.
    - Mark node `u` as visited.
- **Edge Relaxation**: For each neighbor `v` of the selected node `u`:
    - Calculate the time to reach `v` through `u`: `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`.
- **Finalization**: After the loops complete, iterate through the `minTime` array. Any value that is still infinity means the corresponding node is unreachable. Replace these values with `-1`.

## Optimized Dijkstra's Algorithm with Priority Queue
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
- **Graph Representation**: Construct an adjacency list where `adj[i]` contains all neighbors of node `i` and the corresponding edge weights (time).
- **Initialization**: Create a `minTime` array of size `n`, initializing all values to infinity except for `minTime[0]`, which is 0.
- **Priority Queue**: Initialize a min-priority queue to store pairs of `(time, node)`. The priority queue will order elements based on `time`. Insert the starting pair `(0, 0)`.
- **Main Loop**: While the priority queue is not empty:
    - Extract the pair `(t, u)` with the minimum time `t`.
    - If `t` is greater than `minTime[u]`, this is an outdated entry from the queue (a shorter path to `u` has already been processed), so skip it.
- **Edge Relaxation**: For each neighbor `v` of `u` with edge weight `w`:
    - Calculate the potential new time: `newTime = t + w`.
    - **Constraint Check**: If `newTime < disappear[v]` (path is valid) and `newTime < minTime[v]` (path is shorter), then:
        - Update `minTime[v] = newTime`.
        - Add the new pair `(newTime, v)` to the priority queue.
- **Finalization**: After the loop, post-process the `minTime` array. Replace any remaining infinity values with `-1` to indicate unreachable nodes. Return the `minTime` array.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)]

```