We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Time to Visit Disappearing Nodes

Number: 3389

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an undirected weighted graph with n nodes, you start at node 0 and want to determine the minimum time required to reach every node. Each edge is represented as [u, v, length] where length is the travel time between nodes u and v. Additionally, each node i has a disappearance time given by disappear[i]. If you arrive at a node at a time greater than or equal to its disappearance time, you cannot visit it. Return an answer array where answer[i] is the minimum time to reach node i before it disappears or -1 if unreachable.

Key Insights

  • This is a shortest path problem with an extra constraint on the arrival time at nodes.
  • Use Dijkstra's algorithm to find the minimum travel time from the source node.
  • At each step, only relax the edge if the arrival time at the destination is strictly less than its disappearance time.
  • The graph may have multiple edges and can be disconnected.

Space and Time Complexity

Time Complexity: O((E + V) log V) where E is the number of edges and V is the number of nodes. Space Complexity: O(V + E) for the graph representation and O(V) for the distance storage and heap.

Solution

We solve the problem using Dijkstra’s algorithm with a min-heap (priority queue). The modifications compared to the standard Dijkstra are:

  1. Initialize the distance for node 0 as 0 and for all other nodes as infinity.
  2. Use a min-heap which stores pairs of (time, node).
  3. While processing each node from the heap, check if the current time is strictly less than the node’s disappearance time. If not, skip relaxing its edges.
  4. For each adjacent node, if the new accumulated time is less than both its recorded distance and its disappearance time, update the distance and push it onto the heap.
  5. Finally, convert any unreachable nodes (still infinity) to -1 in the result answer.

This method guarantees that we only consider valid arrival times (i.e., before the node disappears) and computes the minimum travel time accordingly.

Code Solutions

import heapq
from collections import defaultdict

def minimumTime(n, edges, disappear):
    # Build graph with lists for each node: (neighbor, travel_time)
    graph = defaultdict(list)
    for u, v, length in edges:
        graph[u].append((v, length))
        graph[v].append((u, length))
    
    # Initialize distances array with infinity and starting point 0
    INF = float('inf')
    dist = [INF] * n
    dist[0] = 0
    
    # Min-heap for Dijkstra: (current_time, current_node)
    heap = [(0, 0)]
    
    while heap:
        cur_time, node = heapq.heappop(heap)
        # If current time is greater than recorded, skip
        if cur_time > dist[node]:
            continue
        # If arriving at node happens at or after it disappears, skip processing
        if cur_time >= disappear[node]:
            continue
        # Process neighbors
        for neighbor, length in graph[node]:
            new_time = cur_time + length
            # Relax if new_time is less than recorded distance and before the neighbor disappears
            if new_time < dist[neighbor] and new_time < disappear[neighbor]:
                dist[neighbor] = new_time
                heapq.heappush(heap, (new_time, neighbor))
    
    # Replace unreachable nodes (still INF) with -1
    return [d if d != INF else -1 for d in dist]

# Example usage:
print(minimumTime(3, [[0,1,2],[1,2,1],[0,2,4]], [1,3,5]))  # Expected [0,2,3]
← Back to All Questions