3112. Minimum Time to Visit Disappearing Nodes

MediumGraphArrayShortest PathHeap (Priority Queue)

Problem Description

There is an undirected graph consisting of n nodes. Each edge is represented by a 2D array edges, where edges[i] = [u_i, v_i, length_i] indicates an edge between node u_i and node v_i with a traversal time of length_i units. Additionally, there's an array disappear, where disappear[i] denotes the time when node i is no longer accessible, meaning you can't visit it after that time.

The graph might be disconnected and could have multiple edges between nodes. The task is to determine the minimum time required to reach each node i starting from node 0. The result should be an array answer, where answer[i] gives the minimum time to reach node i. If node i can't be reached from node 0, answer[i] should be -1.

Intuition

The problem asks us to find the shortest time to reach each node from the starting node 0, considering that some nodes may "disappear" at a certain time, rendering them inaccessible. This requires a combination of shortest path algorithms with constraints tied to node availability over time.

To achieve this, the Dijkstra algorithm is apt for identifying the shortest paths in a weighted graph. Here, we adapt the algorithm by introducing a constraint: we only update the shortest time to node v if the current path satisfies the disappearance time condition (dist[u] + w < disappear[v]).

The key steps include:

Constructing an adjacency list from the edge list for efficient graph representation.
Initializing a distance array where dist[0] = 0 and all other nodes have a distance initialized to infinity.
Employing a priority queue to efficiently fetch the node with the smallest provisional distance.
Iteratively consider each node, explore its neighbors, and update their shortest distances while respecting the disappearance time constraints.
After processing all nodes via the queue, determine the result for each node based on whether it was reachable within its disappearance time.

By carefully updating shortest paths within the limits of node availability, the problem asks us to dynamically evaluate paths in the presence of constraints, leveraging the efficiency of a prioritized search strategy.

Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The solution uses a heap-optimized version of Dijkstra's algorithm to find the shortest paths from node 0 in the graph while considering each node's disappearance time. Here's a detailed breakdown of the approach:

Graph Representation:
- We construct an adjacency list g using the given edge list. For each edge [u_i, v_i, length_i], we append (v_i, length_i) to the adjacency list of u_i and (u_i, length_i) to the adjacency list of v_i. This effectively handles the undirected nature of the graph.
Distance Initialization:
- We create an array dist with size n. The array is initialized such that dist[0] = 0 (since the starting point is node 0) and all other values are set to infinity, representing that they are initially unreachable.
Priority Queue for Efficient Path Finding:
- A priority queue (min-heap) pq is used to always expand the least costly path. Initially, we add the starting node 0 with a distance of 0 to the queue.
Applying Dijkstra's Algorithm with Constraints:
- While the queue is not empty, we extract the node u with the current smallest tentative distance du. If du exceeds dist[u], we skip processing this node as it has already been processed with a shorter path.
- For each neighbor v of node u, we check if the new calculated distance dist[u] + w (here w is the edge weight) is less than dist[v] and also less than disappear[v], the time at which node v disappears. If both conditions are satisfied, we update dist[v] and push (dist[v], v) into the queue.
Generating the Final Answer:
- After processing all nodes, we construct the answer array. For each node i, if dist[i] is less than disappear[i], answer[i] is set to dist[i]; otherwise, answer[i] is set to -1, indicating that node i is unreachable under the constraints.

This approach ensures that we efficiently find the shortest paths while respecting the constraints imposed by the nodes' disappearance over time, utilizing the priority queue to manage the exploration of the graph effectively.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to see how the solution approach works in practice.

Given:

Nodes (n): 4
Edges: [[0, 1, 2], [1, 2, 4], [2, 3, 1], [0, 2, 3]]
Disappear times: [10, 5, 9, 7]

Our goal is to find the minimum time required to reach each node starting from node 0, respecting the disappearance time constraints of each node.

Step-by-step Execution:

Graph Representation:

We create an adjacency list g from the edges:

g = {
  0: [(1, 2), (2, 3)],
  1: [(0, 2), (2, 4)],
  2: [(1, 4), (3, 1), (0, 3)],
  3: [(2, 1)]
}

Distance Initialization:

Initialize dist as [0, INF, INF, INF] where INF symbolizes infinity and 0 because the starting node is node 0.
Priority Queue Setup:

Initialize a priority queue pq and add the starting node: pq = [(0, 0)].
Applying Dijkstra's Algorithm with Constraints:
- Iteration 1:
  - Extract (0, 0) from pq. Current node is 0 with distance 0.
  - Check neighbors:
    - For (1, 2): new_dist = 0 + 2 = 2 which is less than dist[1] (INF) and less than disappear[1] (5). Update dist[1] = 2 and add (2, 1) to pq.
    - For (2, 3): new_dist = 0 + 3 = 3 which is less than dist[2] (INF) and less than disappear[2] (9). Update dist[2] = 3 and add (3, 2) to pq.
- Iteration 2:
  - Extract (2, 1) from pq. Current node is 1 with distance 2.
  - Check neighbors:
    - For (0, 2): new_dist = 2 + 2 = 4 which is not less than dist[0] (0), skip.
    - For (2, 4): new_dist = 2 + 4 = 6 which is not less than dist[2] (3), skip.
- Iteration 3:
  - Extract (3, 2) from pq. Current node is 2 with distance 3.
  - Check neighbors:
    - For (1, 4): new_dist = 3 + 4 = 7 is not less than dist[1] (2), skip.
    - For (3, 1): new_dist = 3 + 1 = 4 which is less than dist[3] (INF) and also less than disappear[3] (7). Update dist[3] = 4 and add (4, 3) to pq.
    - For (0, 3): new_dist = 3 + 3 = 6 which is not less than dist[0] (0), skip.
- Iteration 4:
  - Extract (4, 3) from pq. Current node is 3 with distance 4.
Generating the Final Answer:

The final distance array dist = [0, 2, 3, 4]. Now we need to determine the answer array considering disappear times:
- Node 0: reachable with time 0, 0 < disappear[0] (10), so answer[0] = 0.
- Node 1: reachable with time 2, 2 < disappear[1] (5), so answer[1] = 2.
- Node 2: reachable with time 3, 3 < disappear[2] (9), so answer[2] = 3.
- Node 3: reachable with time 4, 4 < disappear[3] (7), so answer[3] = 4.
Therefore, the final answer is [0, 2, 3, 4].

Solution Implementation

1from typing import List
2from collections import defaultdict
3from heapq import heappop, heappush
4import sys
5
6# Class Solution containing a method to find minimum time to reach each node.
7class Solution:
8    def minimumTime(
9        self, n: int, edges: List[List[int]], disappear: List[int]
10    ) -> List[int]:
11        # Initialize graph as a defaultdict of lists to store adjacency list
12        graph = defaultdict(list)
13      
14        # Populate the graph with bidirectional edges
15        for u, v, weight in edges:
16            graph[u].append((v, weight))
17            graph[v].append((u, weight))
18      
19        # Distance initialization using infinity for easier comparison updates
20        dist = [sys.maxsize] * n  
21        dist[0] = 0
22      
23        # Priority queue initialized with the source node (node 0 and its distance 0)
24        min_heap = [(0, 0)]
25      
26        # Dijkstra's algorithm implementation using a priority queue (min-heap)
27        while min_heap:
28            current_dist, current_node = heappop(min_heap)
29          
30            # If current distance is greater than distance in table, skip
31            if current_dist > dist[current_node]:
32                continue
33          
34            # Check all adjacent nodes to update distances
35            for neighbor, weight in graph[current_node]:
36                # Check if distance through the current node is shorter and valid
37                if dist[neighbor] > dist[current_node] + weight and dist[current_node] + weight < disappear[neighbor]:
38                    # Update distance
39                    dist[neighbor] = dist[current_node] + weight
40                    # Push updated distance and node into the priority queue
41                    heappush(min_heap, (dist[neighbor], neighbor))
42      
43        # Prepare result: if distance is less than disappear time, return it; otherwise, return -1
44        return [d if d < disappear_time else -1 for d, disappear_time in zip(dist, disappear)]
45

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4import java.util.PriorityQueue;
5
6// Define the Solution class
7class Solution {
8  
9    // Method to compute the minimum time to reach each node with disappear constraints
10    public int[] minimumTime(int n, int[][] edges, int[] disappear) {
11      
12        // Create an adjacency list to store the graph
13        List<int[]>[] graph = new List[n];
14      
15        // Initialize each list in the graph
16        Arrays.setAll(graph, k -> new ArrayList<>());
17      
18        // Populate the graph with edges
19        for (int[] edge : edges) {
20            int u = edge[0], v = edge[1], weight = edge[2];
21            graph[u].add(new int[] {v, weight});
22            graph[v].add(new int[] {u, weight});
23        }
24      
25        // Initialize distance array with a large value to represent infinity
26        int[] distances = new int[n];
27        Arrays.fill(distances, 1 << 30);
28        distances[0] = 0;
29      
30        // Priority queue to implement Dijkstra's algorithm
31        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
32        priorityQueue.offer(new int[] {0, 0});
33      
34        // Dijkstra's algorithm to find the shortest paths
35        while (!priorityQueue.isEmpty()) {
36            int[] element = priorityQueue.poll();
37            int currentDistance = element[0], currentNode = element[1];
38          
39            // If the current distance is greater than the stored distance, skip
40            if (currentDistance > distances[currentNode]) {
41                continue;
42            }
43          
44            // Check neighbors of the current node
45            for (int[] neighbor : graph[currentNode]) {
46                int neighborNode = neighbor[0], weight = neighbor[1];
47              
48                // Relaxation step with disappear time constraint
49                if (distances[neighborNode] > distances[currentNode] + weight &&
50                    distances[currentNode] + weight < disappear[neighborNode]) {
51                  
52                    distances[neighborNode] = distances[currentNode] + weight;
53                    priorityQueue.offer(new int[] {distances[neighborNode], neighborNode});
54                }
55            }
56        }
57      
58        // Prepare the result based on distances and disappear constraints
59        int[] result = new int[n];
60        for (int i = 0; i < n; ++i) {
61            result[i] = distances[i] < disappear[i] ? distances[i] : -1;
62        }
63      
64        return result;
65    }
66}
67

1#include <vector>
2#include <queue>
3#include <utility>
4#include <limits>
5
6using namespace std;
7
8class Solution {
9public:
10    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
11        // Create an adjacency list for the graph, where each node has a list of pairs (neighbor, weight)
12        vector<vector<pair<int, int>>> graph(n);
13
14        // Populate the adjacency list with edges
15        for (const auto& edge : edges) {
16            int u = edge[0], v = edge[1], weight = edge[2];
17            graph[u].emplace_back(v, weight);
18            graph[v].emplace_back(u, weight);  // Assuming it's an undirected graph
19        }
20
21        // Initialize distances with a large number (infinity equivalent)
22        vector<int> distance(n, numeric_limits<int>::max());
23        distance[0] = 0;  // Start node (assume 0) has a distance of 0
24
25        // Priority queue to process nodes, ordered by minimum distance (min-heap)
26        using Pair = pair<int, int>;
27        priority_queue<Pair, vector<Pair>, greater<Pair>> pq;
28        pq.emplace(0, 0);  // Starting with node 0
29
30        while (!pq.empty()) {
31            // Get the node with the smallest distance
32            auto [current_distance, current_node] = pq.top();
33            pq.pop();
34
35            // If the current distance is already larger than the known distance, skip it
36            if (current_distance > distance[current_node]) {
37                continue;
38            }
39
40            // Explore neighbors
41            for (auto [neighbor, weight] : graph[current_node]) {
42                int new_distance = distance[current_node] + weight;
43                // Check if a shorter path to 'neighbor' is found and if we don't exceed disappear time
44                if (new_distance < distance[neighbor] && new_distance < disappear[neighbor]) {
45                    distance[neighbor] = new_distance;
46                    pq.emplace(new_distance, neighbor);  // Push updated distance for neighbor
47                }
48            }
49        }
50
51        // Prepare the final answer based on the calculated distances
52        vector<int> answer(n);
53        for (int i = 0; i < n; ++i) {
54            // If the node disappears before or as we reach it, set -1; otherwise, take the calculated distance
55            answer[i] = distance[i] < disappear[i] ? distance[i] : -1;
56        }
57
58        return answer;
59    }
60};
61

1/**
2 * A priority queue interface to be used with Dijkstra's algorithm.
3 */
4interface PriorityQueueElement {
5    value: number[];
6    priority: number;
7}
8
9interface PriorityQueueOptions {
10    compare: (a: number[], b: number[]) => number;
11}
12
13class PriorityQueue {
14    private elements: PriorityQueueElement[] = [];
15    private compare: PriorityQueueOptions['compare'];
16
17    constructor(options: PriorityQueueOptions) {
18        this.compare = options.compare;
19    }
20
21    enqueue(element: number[]) {
22        // Wrap the element with priority
23        const queueElement = { value: element, priority: element[0] };
24        this.elements.push(queueElement);
25        this.upHeap(this.elements.length - 1);
26    }
27
28    dequeue() {
29        if (this.elements.length === 0) return null;
30        const topElement = this.elements[0].value;
31        const lastElement = this.elements.pop();
32        if (this.elements.length !== 0 && lastElement) {
33            this.elements[0] = lastElement;
34            this.downHeap(0);
35        }
36        return topElement;
37    }
38
39    size() {
40        return this.elements.length;
41    }
42
43    private upHeap(index: number) {
44        let currentIndex = index;
45        const element = this.elements[currentIndex];
46        while (currentIndex > 0) {
47            const parentIndex = Math.floor((currentIndex - 1) / 2);
48            const parentElement = this.elements[parentIndex];
49            if (this.compare(element.value, parentElement.value) >= 0) break;
50            this.elements[currentIndex] = parentElement;
51            currentIndex = parentIndex;
52        }
53        this.elements[currentIndex] = element;
54    }
55
56    private downHeap(index: number) {
57        const length = this.elements.length;
58        const element = this.elements[index];
59        let currentIndex = index;
60
61        while (true) {
62            let leftChildIndex = 2 * currentIndex + 1;
63            let rightChildIndex = 2 * currentIndex + 2;
64            let smallestIndex = currentIndex;
65
66            if (leftChildIndex < length && this.compare(this.elements[leftChildIndex].value, this.elements[smallestIndex].value) < 0) {
67                smallestIndex = leftChildIndex;
68            }
69            if (rightChildIndex < length && this.compare(this.elements[rightChildIndex].value, this.elements[smallestIndex].value) < 0) {
70                smallestIndex = rightChildIndex;
71            }
72            if (smallestIndex === currentIndex) break;
73
74            this.elements[currentIndex] = this.elements[smallestIndex];
75            this.elements[smallestIndex] = element;
76            currentIndex = smallestIndex;
77        }
78    }
79}
80
81/**
82 * Calculate the minimum time to reach each node in a graph 
83 * considering certain nodes disappear after some time.
84 * 
85 * @param n - Number of nodes.
86 * @param edges - Array of edges, each represented by [u, v, w] where u and v are nodes and w is weight.
87 * @param disappear - Time after which each node disappears.
88 * @returns Array of minimum times or -1 if not reachable before disappearance.
89 */
90function minimumTime(n: number, edges: number[][], disappear: number[]): number[] {
91    // Build adjacency list for the graph
92    const graph: [number, number][][] = Array.from({ length: n }, () => []);
93    for (const [u, v, w] of edges) {
94        graph[u].push([v, w]);
95        graph[v].push([u, w]);
96    }
97
98    // Initialize distances as infinite, with the start node (0) distance set to 0
99    const dist = Array.from({ length: n }, () => Infinity);
100    dist[0] = 0;
101
102    // Priority Queue for processing nodes based on shortest path first
103    const pq = new PriorityQueue({
104        compare: (a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]),
105    });
106    pq.enqueue([0, 0]);
107
108    // Dijkstra's Algorithm: While queue is not empty, process nodes
109    while (pq.size() > 0) {
110        const [currentDist, currentNode] = pq.dequeue()!;
111        if (currentDist > dist[currentNode]) {
112            // Skip nodes already processed with shorter paths
113            continue;
114        }
115        for (const [nextNode, weight] of graph[currentNode]) {
116            const newDist = currentDist + weight;
117            // Check if the new calculated distance is less than the current,
118            // and ensure it won't reach after the node disappears
119            if (newDist < dist[nextNode] && newDist < disappear[nextNode]) {
120                dist[nextNode] = newDist;
121                pq.enqueue([newDist, nextNode]);
122            }
123        }
124    }
125
126    // Map the results: return the shortest path or -1 if node disappears before reaching
127    return dist.map((time, index) => (time < disappear[index] ? time : -1));
128}
129

Time and Space Complexity

The time complexity of the code is O(m \times \log n), where m is the number of edges and n is the number of nodes in the graph. This complexity arises from the use of Dijkstra's algorithm, specifically from maintaining and processing a priority queue with heappop and heappush operations, which each take O(\log n) time and are executed m times in the worst-case scenario.

The space complexity of the code is O(m + n), accounting for the storage of the graph in an adjacency list (O(m)) and the distance array (O(n)).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function call

Determine return value

Determine how many recursive calls will be made

Tracing the recursive calls