Problem Description

You have an undirected graph with n nodes (numbered from 0 to n-1). The graph is described by a 2D array edges, where each element edges[i] = [ui, vi, lengthi] represents an edge between nodes ui and vi that takes lengthi units of time to traverse.

There's a time constraint: each node i disappears from the graph at time disappear[i]. Once a node disappears, you cannot visit it anymore.

Starting from node 0, you need to find the minimum time required to reach each node in the graph. If you reach a node at exactly the time it disappears or later, you cannot visit that node.

The graph may have these characteristics:

• It might be disconnected (not all nodes are reachable from node 0)
• It might contain multiple edges between the same pair of nodes

Your task is to return an array answer where:

• answer[i] is the minimum time needed to reach node i from node 0
• answer[i] is -1 if node i cannot be reached from node 0 (either because there's no path or because the node disappears before you can reach it)

For example, if the shortest path to node i takes 10 units of time but disappear[i] = 10, then node i is unreachable because it disappears at the exact moment you would arrive.

Intuition

This problem is asking for the shortest path from a source node (node 0) to all other nodes, which immediately suggests using a shortest path algorithm. The classic choice for this is Dijkstra's algorithm.

However, there's a twist - nodes have a "disappearance time." This means we need to consider not just the shortest path, but also whether we can reach a node before it disappears. If we arrive at a node at time t and the node disappears at time disappear[i], we can only visit the node if t < disappear[i].

The key insight is that we can modify Dijkstra's algorithm to handle this constraint. During the relaxation step, when we consider updating the distance to a neighbor node v through node u, we need to check two conditions:

1. The new distance dist[u] + w is shorter than the current known distance dist[v]
2. We can reach node v before it disappears: dist[u] + w < disappear[v]

Only when both conditions are met should we update the distance and continue exploring from that node.

Why does Dijkstra's algorithm work here? Because:

• We're dealing with non-negative edge weights (time cannot be negative)
• We want the minimum time to reach each node
• The disappearance constraint doesn't change the fundamental property that once we've found the shortest path to a node, we don't need to revisit it

The algorithm naturally handles disconnected components - nodes that cannot be reached from node 0 will retain their initial infinite distance. Similarly, nodes that disappear before we can reach them won't have their distances updated, also remaining at infinity. In the final step, we convert these infinite distances to -1 as required by the problem.

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

Solution Approach

The solution implements a heap-optimized version of Dijkstra's algorithm with modifications to handle node disappearance times.

Step 1: Build the Graph

First, we construct an adjacency list representation of the graph using a defaultdict(list). For each edge [u, v, w], we add the connection in both directions since the graph is undirected:

• Add (v, w) to g[u]
• Add (u, w) to g[v]

Step 2: Initialize Distance Array

We create a distance array dist of size n, initialized with infinity (inf) for all nodes except the source node. Set dist[0] = 0 since the distance from node 0 to itself is 0.

Step 3: Priority Queue Setup

Initialize a min-heap priority queue pq with the tuple (0, 0), representing (distance, node). The heap ensures we always process the node with the smallest distance first.

Step 4: Modified Dijkstra's Algorithm

While the priority queue is not empty:

1. Extract minimum: Pop the node u with the smallest distance du from the heap using heappop(pq).

2. Skip outdated entries: If du > dist[u], this entry is outdated (we've already found a shorter path to u), so skip it and continue.

3. Relax edges: For each neighbor v of node u with edge weight w:

   • Calculate the new potential distance: new_dist = dist[u] + w
   • Check two conditions:
     • Is this path shorter? dist[v] > new_dist
     • Can we reach v before it disappears? new_dist < disappear[v]
   • If both conditions are satisfied:
     • Update dist[v] = new_dist
     • Push (dist[v], v) to the priority queue

Step 5: Format the Result

After processing all reachable nodes, construct the final answer array. For each node i:

• If dist[i] < disappear[i], the node is reachable before it disappears, so answer[i] = dist[i]
• Otherwise, the node is unreachable, so answer[i] = -1

The list comprehension [a if a < b else -1 for a, b in zip(dist, disappear)] elegantly handles this conversion, where nodes with infinite distance or those that disappear before we can reach them are marked as -1.

Time Complexity: O((E + V) log V) where E is the number of edges and V is the number of vertices, due to the heap operations.

Space Complexity: O(V + E) for storing the graph and distance array.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example Input:

• n = 4 (nodes: 0, 1, 2, 3)
• edges = [[0,1,2], [0,2,4], [1,2,1], [2,3,3]]
• disappear = [10, 5, 8, 1]

Step 1: Build the Graph

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

Step 2: Initialize Distance Array

dist = [0, inf, inf, inf]

Step 3: Priority Queue Setup

pq = [(0, 0)]  # (distance, node)

Step 4: Modified Dijkstra's Algorithm

Iteration 1:

• Pop (0, 0) from pq
• Process node 0 with distance 0
• Check neighbors:
  • Node 1: new_dist = 0 + 2 = 2
    • 2 < inf? ✓
    • 2 < disappear[1]=5? ✓
    • Update: dist[1] = 2, push (2, 1) to pq
  • Node 2: new_dist = 0 + 4 = 4
    • 4 < inf? ✓
    • 4 < disappear[2]=8? ✓
    • Update: dist[2] = 4, push (4, 2) to pq
• State: dist = [0, 2, 4, inf], pq = [(2,1), (4,2)]

Iteration 2:

• Pop (2, 1) from pq
• Process node 1 with distance 2
• Check neighbors:
  • Node 0: new_dist = 2 + 2 = 4 (skip, 4 > dist[0]=0)
  • Node 2: new_dist = 2 + 1 = 3
    • 3 < 4? ✓
    • 3 < disappear[2]=8? ✓
    • Update: dist[2] = 3, push (3, 2) to pq
• State: dist = [0, 2, 3, inf], pq = [(3,2), (4,2)]

Iteration 3:

• Pop (3, 2) from pq
• Process node 2 with distance 3
• Check neighbors:
  • Node 0: new_dist = 3 + 4 = 7 (skip, 7 > dist[0]=0)
  • Node 1: new_dist = 3 + 1 = 4 (skip, 4 > dist[1]=2)
  • Node 3: new_dist = 3 + 3 = 6
    • 6 < inf? ✓
    • 6 < disappear[3]=1? ✗ (Node 3 disappears at time 1!)
    • Do not update
• State: dist = [0, 2, 3, inf], pq = [(4,2)]

Iteration 4:

• Pop (4, 2) from pq
• This is outdated (4 > dist[2]=3), skip

Step 5: Format the Result

dist = [0, 2, 3, inf]
disappear = [10, 5, 8, 1]

• Node 0: 0 < 10 ✓ → answer[0] = 0
• Node 1: 2 < 5 ✓ → answer[1] = 2
• Node 2: 3 < 8 ✓ → answer[2] = 3
• Node 3: inf (unreachable) → answer[3] = -1

Final Answer: [0, 2, 3, -1]

Node 3 is unreachable because even though there's a path (0→2→3) that would take 6 time units, node 3 disappears at time 1, making it impossible to reach.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × log m) where m is the number of edges.

The algorithm uses Dijkstra's shortest path algorithm with a min-heap. Breaking down the operations:

• Building the adjacency list from edges takes O(m) time
• Each edge can be processed at most twice (once from each endpoint), resulting in at most 2m heap operations
• Each heap operation (push/pop) takes O(log k) where k is the heap size, which can be at most O(m) in the worst case
• Therefore, the total time complexity is O(m × log m)

Space Complexity: O(m) where m is the number of edges.

The space usage consists of:

• The adjacency list g stores all edges twice (once for each direction), using O(m) space
• The distance array dist uses O(n) space
• The priority queue pq can contain at most O(m) entries in the worst case
• Since in a connected graph n ≤ m + 1, and we need at least n - 1 edges to connect n nodes, the dominant term is O(m)
• Therefore, the total space complexity is O(m)

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

Common Pitfalls

1. Not Handling Multiple Edges Between Same Nodes

The problem explicitly states that the graph might contain multiple edges between the same pair of nodes. A common mistake is assuming there's only one edge between any two nodes and overwriting edges instead of keeping all of them.

Incorrect approach:

# Wrong: This overwrites previous edges
graph = {}
for u, v, weight in edges:
    graph[u] = (v, weight)  # Overwrites!
    graph[v] = (u, weight)  # Overwrites!

Correct approach:

# Correct: Keep all edges, even duplicates
graph = defaultdict(list)
for u, v, weight in edges:
    graph[u].append((v, weight))  # Appends all edges
    graph[v].append((u, weight))  # Appends all edges

2. Incorrect Disappearance Time Check

A critical pitfall is misunderstanding when a node becomes unreachable. The problem states that if you reach a node at exactly the time it disappears or later, you cannot visit it.

Incorrect approach:

# Wrong: Allows visiting at disappearance time
if new_distance <= disappear[neighbor]:  # Should be strict <
    distances[neighbor] = new_distance

Correct approach:

# Correct: Must arrive strictly before disappearance
if new_distance < disappear[neighbor]:  # Strict inequality
    distances[neighbor] = new_distance

3. Not Checking Disappearance Time in Final Result

Even if node 0 has the shortest path calculated, we must verify it's reachable before it disappears. A common mistake is forgetting to check the disappearance constraint when building the final answer.

Incorrect approach:

# Wrong: Returns raw distances without checking disappearance
return [d if d != inf else -1 for d in distances]

Correct approach:

# Correct: Checks both infinity AND disappearance time
result = []
for distance, disappear_time in zip(distances, disappear):
    if distance < disappear_time:  # Must check disappearance
        result.append(distance)
    else:
        result.append(-1)

4. Starting Node Disappearance Edge Case

If disappear[0] == 0, the starting node itself disappears immediately, making the entire graph unreachable. The solution should handle this gracefully.

Solution: The current implementation handles this correctly because the condition new_distance < disappear[neighbor] will prevent any exploration if the starting node has already disappeared, resulting in all nodes (including node 0) being marked as -1 in the final result.