Abstract / Summary

Find the shortest path in a graph where nodes disappear after being visited, starting from a given node.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 38% (70k+ submissions).

Typical patterns to solve this problem:

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

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The minimumTime method computes, for every vertex in an undirected weighted graph, the earliest moment at which the vertex can be reached starting from vertex 0. Each vertex has an associated “disappear” time; a vertex cannot be visited after that moment. The algorithm returns an array where the i-th entry is the earliest reachable time for vertex i, or -1 if the vertex cannot be reached before it disappears.

The implementation follows a Dijkstra-style expansion using a min-heap, but it incorporates the disappear constraint directly into the relaxation step. The result array is filled incrementally as vertices are extracted from the heap, guaranteeing that the first time a vertex is processed corresponds to its minimum reachable time.

Graph Construction

The first phase builds an adjacency list from the edge list. Each edge is undirected, so both directions are stored.

graph = [ [] for _ in range(n) ]
for u, v, length in edges:
    graph[u].append(( v, length ))
    graph[v].append(( u, length ))

Using a list of lists provides constant-time access to a vertex’s neighbors and avoids the overhead of dictionary lookups.

Result and Expectation Initialization

Two auxiliary arrays are prepared. result holds the final answer, initialized to -1 to denote “unreached”. expect tracks the smallest tentative arrival time that has been pushed onto the heap for each vertex; it starts at positive infinity.

result = [ -1 ] * n
expect = [ +inf ] * n

The expect array enables a cheap check that prevents the heap from being flooded with dominated entries.

Heap-Driven Exploration

A min-heap (todo) stores pairs (time, node). The algorithm begins with the source vertex 0 at time 0.

todo = [ ( 0, 0 ) ]   # min-heap: (time, node)
while todo:
    now, node = heappop(todo)

Skipping Processed Vertices

If a vertex has already been assigned a definitive arrival time, any later heap entry for that vertex is ignored. This early-exit check eliminates unnecessary work.

if result[node] != -1:
    continue

Recording the First Arrival

When a vertex is popped for the first time, its earliest reachable time is fixed in result.

result[node] = now

Because the heap always yields the smallest pending time, this assignment is guaranteed to be optimal.

Relaxation with Disappear Constraint

For each neighbor, the algorithm computes the arrival time arrive. The neighbor is only considered if this arrival occurs strictly before both the neighbor’s current best tentative time (expect[next]) and its disappear deadline (disappear[next]). If the condition holds, the neighbor is pushed onto the heap and expect is updated.

for next, duration in graph[node]:
    arrive = now + duration
    if arrive < min(expect[next], disappear[next]):
        heappush(todo, ( arrive, next ))
        expect[next] = arrive

The min expression simultaneously enforces two constraints: it prevents revisiting a vertex with a later time than already known, and it respects the vertex’s disappear limit. Consequently, vertices that would be reached after they have vanished are never enqueued.

Edge Cases Handled

• Vertices that are isolated or lie behind a chain of edges whose cumulative length exceeds the vertex’s disappear time never satisfy the relaxation condition, so they remain -1 in the final array.
• A vertex whose disappear time is zero can only be reached if it is the source (time 0); otherwise the arrive < disappear[next] test blocks any entry.
• Multiple edges between the same pair of vertices are accommodated because each edge contributes a separate entry in the adjacency list; the expect array ensures that only the earliest viable arrival is propagated.
• The algorithm gracefully handles an empty graph (n == 0) by returning an empty list, as the initializations produce zero-length structures and the while-loop never executes.

Performance Optimizations

The adjacency list representation reduces memory overhead compared with a full matrix and enables fast iteration over incident edges. The use of a binary heap (heappush/heappop) provides logarithmic time extraction and insertion, which is essential for scaling to large edge sets.

The expect array acts as a lightweight pruning mechanism. By recording the smallest time ever pushed for each vertex, the algorithm avoids inserting dominated entries that would later be discarded by the “already processed” check. This reduces the number of heap operations and the overall work performed during the relaxation phase.

Early termination of processed vertices (if result[node] != -1: continue) prevents the algorithm from revisiting vertices that have already attained their optimal time, further limiting unnecessary neighbor exploration.

Collectively, these choices keep the execution focused on promising paths and minimize redundant work, delivering an efficient solution for the minimum-time-with-deadline problem.

Imagine there is a big map of different places connected by paths and each path takes some time to travel across. Some of these places are special because they vanish after a certain amount of time, so you have to reach them before they disappear forever.

The code starts by making a long list to keep track of the earliest time you arrive at each place. Everyone starts at the beginning point at time zero. There is a special helper called a heap that acts like a waiting line. It always tells you which place is the quickest to visit next.

When you decide to visit a place, you check if it is still there. If it is already gone, you simply skip it. If it is still waiting for you, you record the exact time you arrived. Then, you look at all the paths connected to that spot. You peek at the next stop to see if you can get there before it disappears. If you can make it in time, you add that new destination to the waiting line to visit later. You keep doing this until you have checked everywhere you can possibly go. Every time you reach a new spot, you write down how long it took so you always remember the fastest way to get there.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python	TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java	Go	Python	TS
	Progiez	C++		Java		Python
github	charles-wangkai			Java
	everthis		JS
	fsq	C++
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality