LeetCode 3604 - Minimum Time to Reach Destination in Directed Graph

Difficulty: 🟡 Medium
Topics: Graph Theory, Heap (Priority Queue), Shortest Path

Solution

Problem Understanding

This problem asks us to compute the minimum time required to reach the last node in a directed graph where each edge has a time window constraint. You start at node 0 at time 0, and each edge [u, v, start, end] can only be used if you traverse it at an integer time t such that start <= t <= end. At each time unit, you can either wait at your current node or take a valid outgoing edge.

The input consists of an integer n representing the number of nodes and a list of edges with start and end availability times. The output is the minimum time to reach node n - 1, or -1 if it's impossible.

Constraints highlight that the graph can be very large (n and edges.length up to 10^5), and edge availability times can be extremely high (up to 10^9). This eliminates naive exhaustive simulations because iterating over every possible time is infeasible.

Key edge cases include:

No outgoing edges from node 0 (immediate impossibility).
Edges that only become available after a delay, requiring waiting.
Multiple edges between the same nodes with overlapping or non-overlapping time intervals.

The problem essentially combines shortest-path computation with time-window constraints, requiring a careful approach.

Approaches

Brute Force

A brute-force approach would simulate all possible paths and all integer times, tracking the earliest time to reach each node. You could imagine using BFS or DFS, and for each node, simulate waiting until a valid edge is available. While this is conceptually simple and correct, the time complexity is prohibitive because waiting could extend up to 10^9, and the number of paths could be exponential in n. Thus, this approach cannot work within the constraints.

Optimal Approach

The key insight is that we can treat this as a modified shortest-path problem where the "distance" is time, and we can only traverse an edge if the current time is within the edge's [start, end] interval. This naturally suggests Dijkstra’s algorithm using a priority queue (min-heap), but we need to account for waiting:

Track the earliest known arrival time to each node.
Use a min-heap to always explore the node with the current earliest time.
For each outgoing edge, compute the next possible traversal time as max(current_time, start). If this exceeds end, skip the edge. Otherwise, add 1 to traverse the edge and push the neighbor into the heap if it improves the earliest time.

This ensures we always consider the optimal waiting and traversal sequence, without simulating every integer time explicitly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * T)	O(n)	Simulate all paths and all possible waiting times (T is max end time)
Optimal	O(E log n)	O(E + n)	Modified Dijkstra using earliest arrival times and priority queue

Algorithm Walkthrough

Graph Construction: Build an adjacency list mapping each node to its outgoing edges with time intervals. This allows quick lookup of neighbors.
Initialization: Create an array earliest of size n to track the minimum arrival time at each node, initializing all values to infinity, except earliest[0] = 0. Initialize a min-heap with (0, 0) representing (current_time, node).
Heap Processing: While the heap is not empty:

a. Pop (current_time, node) from the heap.

b. Skip if current_time is greater than earliest[node] since we have already found a faster way.

c. For each outgoing edge (node → neighbor, start, end):

i. Compute next_time = max(current_time, start) + 1.

ii. If next_time - 1 > end, skip because the edge is unavailable.

iii. If next_time < earliest[neighbor], update earliest[neighbor] = next_time and push (next_time, neighbor) into the heap. 4. Return Result: After heap processing, check earliest[n-1]. If it is still infinity, return -1. Otherwise, return earliest[n-1].

Why it works: This algorithm maintains the invariant that the heap always processes nodes in order of increasing arrival time. Waiting at a node is implicitly handled by max(current_time, start), ensuring we never attempt edges too early. The priority queue guarantees the earliest arrival times propagate optimally.

Python Solution

from typing import List
import heapq

class Solution:
    def minTime(self, n: int, edges: List[List[int]]) -> int:
        from collections import defaultdict
        
        graph = defaultdict(list)
        for u, v, start, end in edges:
            graph[u].append((v, start, end))
        
        earliest = [float('inf')] * n
        earliest[0] = 0
        
        heap = [(0, 0)]  # (current_time, node)
        
        while heap:
            current_time, node = heapq.heappop(heap)
            if current_time > earliest[node]:
                continue
            
            for neighbor, start, end in graph[node]:
                if current_time > end:
                    continue
                next_time = max(current_time, start) + 1
                if next_time <= end + 1 and next_time < earliest[neighbor]:
                    earliest[neighbor] = next_time
                    heapq.heappush(heap, (next_time, neighbor))
        
        return earliest[n-1] if earliest[n-1] != float('inf') else -1

The Python implementation closely follows the algorithm walkthrough. The max(current_time, start) + 1 ensures we wait if necessary. The heap ensures we always explore the node with the earliest possible arrival time.

Go Solution

package main

import (
    "container/heap"
    "math"
)

type Edge struct {
    to, start, end int
}

type Item struct {
    node, time int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].time < pq[j].time }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x any) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() any {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func minTime(n int, edges [][]int) int {
    graph := make([][]Edge, n)
    for _, e := range edges {
        u, v, start, end := e[0], e[1], e[2], e[3]
        graph[u] = append(graph[u], Edge{v, start, end})
    }

    earliest := make([]int, n)
    for i := range earliest {
        earliest[i] = math.MaxInt64
    }
    earliest[0] = 0

    pq := &PriorityQueue{}
    heap.Init(pq)
    heap.Push(pq, Item{0, 0})

    for pq.Len() > 0 {
        curr := heap.Pop(pq).(Item)
        node, currTime := curr.node, curr.time
        if currTime > earliest[node] {
            continue
        }

        for _, edge := range graph[node] {
            if currTime > edge.end {
                continue
            }
            nextTime := max(currTime, edge.start) + 1
            if nextTime <= edge.end+1 && nextTime < earliest[edge.to] {
                earliest[edge.to] = nextTime
                heap.Push(pq, Item{edge.to, nextTime})
            }
        }
    }

    if earliest[n-1] == math.MaxInt64 {
        return -1
    }
    return earliest[n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

In Go, we explicitly define a priority queue struct. Slices are used for graph adjacency lists, and math.MaxInt64 represents infinity. Otherwise, the logic mirrors Python.

Worked Examples

Example 1

n = 3, edges = [[0,1,0,1],[1,2,2,5]]

Step	Heap	Current Node	Current Time	Actions	Heap After
Init	[(0,0)]	0	0	Edge 0→1 valid at t=0	[(1,1)]
1	[(1,1)]	1	1	Wait until 2, Edge 1→2 valid	[(3,2)]
2	[(3,2)]	2	3	Reached target	-

Minimum time = 3

Example 2

`n = 4, edges = [[0,1,0,3],[1,3,7,8],[