#3341
Find Minimum Time to Reach Last Room I
MediumArrayGraph TheoryHeap (Priority Queue)MatrixShortest PathGraph TraversalDijkstra's AlgorithmPriority Queue
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n*m log(n*m)) |
| Space | O(1) | O(n*m) |
💡
Intuition
Time O(n*m log(n*m))Space O(n*m)
The optimal solution uses Dijkstra's algorithm to efficiently find the shortest path in a weighted graph, where the weights are the waiting times in each room.
⚙️
Algorithm
3 steps- 1Step 1: Initialize a priority queue to explore rooms based on the earliest time they can be reached.
- 2Step 2: Start from (0, 0) and push it into the queue with time 0.
- 3Step 3: While the queue is not empty, pop the room with the smallest time, and explore its adjacent rooms, updating their times if a shorter path is found.
solution.py19 lines
1import heapq
2
3def minTime(moveTime):
4 n, m = len(moveTime), len(moveTime[0])
5 pq = [(0, 0, 0)] # (time, x, y)
6 visited = set()
7 while pq:
8 current_time, x, y = heapq.heappop(pq)
9 if (x, y) in visited:
10 continue
11 visited.add((x, y))
12 if x == n - 1 and y == m - 1:
13 return current_time
14 for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
15 nx, ny = x + dx, y + dy
16 if 0 <= nx < n and 0 <= ny < m:
17 wait_time = max(0, moveTime[nx][ny] - current_time)
18 heapq.heappush(pq, (current_time + wait_time + 1, nx, ny))
19 return -1ℹ
Complexity note: The time complexity is O(n*m log(n*m)) due to the priority queue operations, where n*m is the number of rooms.
- 1The waiting time in each room significantly affects the total time to reach the destination.
- 2Using a priority queue allows us to efficiently explore the shortest paths first.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.