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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Time to Visit Disappearing Nodes

Difficulty: Medium

Problem Description

There is an undirected graph of n nodes. You are given a 2D array edges, where edges[i] = [u_i, v_i, length_i] describes an edge between node u_i and node v_i with a traversal time of length_i 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. 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.

Key Insights

  • The problem involves finding the shortest path in a weighted undirected graph.
  • Each node has a specific time at which it disappears, which adds a constraint to the traversal.
  • We can use Dijkstra's algorithm to find the shortest path while checking the disappearance times.
  • Nodes that cannot be reached within their disappearance time should return -1.

Space and Time Complexity

Time Complexity: O((V + E) log V), where V is the number of nodes and E is the number of edges.
Space Complexity: O(V + E) for the graph representation and O(V) for the priority queue.

Solution

To solve this problem, we will utilize Dijkstra's algorithm which is suitable for graphs with non-negative weights. We will maintain a priority queue to explore the nodes based on the shortest time taken to reach them. As we traverse the graph, we will check if the current time exceeds the disappearance time of the node being visited. If it does, we disregard that path. Otherwise, we update the minimum time to reach that node if the current time is less than the previously recorded time.

  1. Initialize a priority queue (min-heap) to keep track of the nodes to be explored based on the time taken to reach them.
  2. Create a list to store the minimum time to reach each node, initialized to infinity.
  3. Start from node 0 with a time of 0, pushing it onto the priority queue.
  4. While the priority queue is not empty, pop the node with the smallest time.
  5. For each neighboring node, calculate the time to reach it and compare it with its disappearance time. If it is reachable within that time, update the minimum time and push it onto the queue.
  6. Return the list of minimum times or -1 for unreachable nodes.

Code Solutions

import heapq
from collections import defaultdict

def min_time_to_visit_disappearing_nodes(n, edges, disappear):
    graph = defaultdict(list)
    # Build the graph
    for u, v, length in edges:
        graph[u].append((v, length))
        graph[v].append((u, length))

    min_time = [float('inf')] * n
    min_time[0] = 0
    pq = [(0, 0)]  # (time, node)

    while pq:
        current_time, node = heapq.heappop(pq)

        # If the current_time exceeds disappearance time, skip
        if current_time >= disappear[node]:
            continue

        for neighbor, travel_time in graph[node]:
            new_time = current_time + travel_time

            # If we can reach the neighbor before it disappears
            if new_time < disappear[neighbor]:
                if new_time < min_time[neighbor]:  # Shorter path found
                    min_time[neighbor] = new_time
                    heapq.heappush(pq, (new_time, neighbor))

    # Replace inf with -1 for unreachable nodes
    return [time if time != float('inf') else -1 for time in min_time]
← Back to All Questions