How to Solve Minimum Time to Visit Disappearing Nodes

Start from node 0 and calculate the shortest path to each node using a modified Dijkstra's algorithm that respects node disappearance times. Nodes are only considered reachable if the current traversal time is less than their disappear time. The solution balances array storage and priority queue management to handle graph traversal efficiently while avoiding inaccessible nodes.

Problem Statement

You are given an undirected graph of n nodes labeled from 0 to n-1. The graph is defined by a list of edges, where edges[i] = [ui, vi, lengthi] represents a bidirectional edge between nodes ui and vi that takes lengthi units of time to traverse. Each node i has a disappear time given in the array disappear, indicating the time at which the node vanishes and can no longer be visited. Your task is to determine the minimum time required to reach each node from node 0 before it disappears, returning -1 if a node cannot be reached in time.

The graph may be disconnected and can contain multiple edges between the same pair of nodes. You must compute the minimum traversal times for all nodes while ensuring no node is visited after its disappearance time. Optimize your solution to handle large graphs efficiently using arrays and priority queues, taking the disappearance constraints into account.

Examples

Example 1

Input: n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]

Output: [0,-1,4]

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.

Example 2

Input: n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,3,5]

Output: [0,2,3]

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.

Example 3

Input: n = 2, edges = [[0,1,1]], disappear = [1,1]

Output: [0,-1]

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

Solution Approach

Graph Construction

Build an adjacency list from the edges array. Store for each node the connected nodes along with the traversal times. Handle multiple edges by keeping the shortest traversal time for each pair to simplify Dijkstra processing.

Modified Dijkstra Traversal

Use a priority queue to explore nodes based on the earliest arrival time. Only push a node into the queue if the accumulated time is less than its disappear time. This ensures nodes that vanish cannot be incorrectly reached.

Result Compilation

Initialize the result array with -1 for all nodes. Update each node's minimum reachable time as it is popped from the priority queue. Nodes that remain -1 are unreachable due to disappearance or disconnected components.

Complexity Analysis

Time complexity depends on the number of nodes and edges processed in the priority queue, generally O((n + edges.length) log n). Space complexity is dominated by the adjacency list, priority queue, and result array, typically O(n + edges.length).

What Interviewers Usually Probe

• Check whether the candidate correctly handles nodes that disappear before being reached.
• Listen for usage of priority queue with Dijkstra to manage earliest arrival times.
• Watch if the candidate optimizes multiple edges between nodes efficiently.

Common Pitfalls or Variants

Common pitfalls

• Forgetting to compare current traversal time with node disappear time, causing incorrect reachable nodes.
• Not handling multiple edges between the same nodes properly, leading to suboptimal paths.
• Assuming the graph is connected and not accounting for unreachable nodes.

Follow-up variants

• Nodes disappear at random intervals instead of a fixed array, requiring dynamic updates during traversal.
• Edges may have time-dependent weights, increasing complexity of minimum arrival computation.
• Start node is not fixed at 0, requiring generalized multi-source shortest path handling.

How GhostInterview Helps

• Provides a step-by-step modified Dijkstra implementation tailored for disappearing-node constraints.
• Highlights early pruning strategies in the priority queue to skip unreachable nodes efficiently.
• Offers concrete examples showing why standard shortest path fails if disappear times are ignored.

Topic Pages

• Array
• Graph
• Heap (Priority Queue)
• Shortest Path

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the key strategy to solve Minimum Time to Visit Disappearing Nodes efficiently?

Use a priority queue with Dijkstra's algorithm, only visiting nodes if current time is less than their disappear time.

How should multiple edges between the same nodes be handled?

Keep only the edge with the shortest traversal time to avoid suboptimal paths and unnecessary queue processing.

Can a node ever be visited after its disappear time?

No, nodes that disappear before arrival are considered unreachable and should remain -1 in the result.

Does the graph need to be connected to solve this problem?

No, disconnected nodes are allowed. Unreachable nodes will correctly remain marked as -1.

Which data structures are essential for this array plus graph problem?

An adjacency list for graph representation, an array for disappear times and results, and a priority queue for earliest arrival traversal.