Tejav
#3604

Minimum Time to Reach Destination in Directed Graph

Medium
Graph TheoryHeap (Priority Queue)Shortest PathGraph TraversalPriority QueueShortest Path Algorithms
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(E log V)
Space
O(1)
O(V)
💡

Intuition

Time O(E log V)Space O(V)

Use a modified Dijkstra's algorithm to find the shortest time to reach the destination by treating each state as a combination of the current node and time.

⚙️

Algorithm

3 steps
  1. 1Step 1: Initialize a priority queue with (0, 0) for starting at node 0 at time 0.
  2. 2Step 2: While the queue is not empty, extract the minimum time state and explore outgoing edges.
  3. 3Step 3: For each edge, check if the current time allows travel, update the time if a shorter path is found, and push the new state into the queue.
solution.py24 lines
1import heapq
2
3def minTime(n, edges):
4    graph = {}
5    for u, v, start, end in edges:
6        if u not in graph:
7            graph[u] = []
8        graph[u].append((v, start, end))
9    pq = [(0, 0)]
10    min_time = {i: float('inf') for i in range(n)}
11    min_time[0] = 0
12    while pq:
13        t, u = heapq.heappop(pq)
14        if u == n - 1:
15            return t
16        for v, start, end in graph.get(u, []):
17            if t <= end:
18                wait_time = max(0, start - t)
19                new_time = t + wait_time + 1
20                if new_time < min_time[v]:
21                    min_time[v] = new_time
22                    heapq.heappush(pq, (new_time, v))
23    return -1
24
ℹ

Complexity note: The complexity comes from the priority queue operations and edge explorations, where E is the number of edges and V is the number of nodes.

  • 1Understanding edge availability based on time is crucial.
  • 2Waiting can be strategically used to optimize travel time.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.