There is a dungeon with n x m rooms arranged as a grid.
You are given a 2D array moveTime of size n x m, where moveTime[i][j] represents the minimum time in seconds when you can start moving to that room. You start from the room (0, 0) at time t = 0 and can move to an adjacent room. Moving between adjacent rooms takes exactly one second.
Return the minimum time to reach the room (n - 1, m - 1).
Two rooms are adjacent if they share a common wall, either horizontally or vertically.
Example 1:
Input: moveTime = [[0,4],[4,4]]
Output: 6
Explanation:
The minimum time required is 6 seconds.
t == 4, move from room (0, 0) to room (1, 0) in one second.t == 5, move from room (1, 0) to room (1, 1) in one second.Example 2:
Input: moveTime = [[0,0,0],[0,0,0]]
Output: 3
Explanation:
The minimum time required is 3 seconds.
t == 0, move from room (0, 0) to room (1, 0) in one second.t == 1, move from room (1, 0) to room (1, 1) in one second.t == 2, move from room (1, 1) to room (1, 2) in one second.Example 3:
Input: moveTime = [[0,1],[1,2]]
Output: 3
Constraints:
2 <= n == moveTime.length <= 502 <= m == moveTime[i].length <= 500 <= moveTime[i][j] <= 109Problem Overview: You are given a grid where each cell represents a room and contains the earliest time you are allowed to enter it. Starting from the top-left room, you can move up, down, left, or right. The goal is to compute the minimum time required to reach the bottom-right room while respecting each room’s time constraint.
Approach 1: Breadth-First Search (BFS) with Time Adjustment (Time: O(m * n), Space: O(m * n))
This approach models the grid as a graph and explores rooms using graph traversal. A queue processes cells level by level while tracking the current time needed to reach each position. When moving to a neighbor, you check whether the arrival time is earlier than the room’s allowed time. If it is, you wait until the room becomes available before continuing. Each room is visited with the earliest feasible arrival time, and a visited or distance matrix prevents redundant processing.
This BFS-style traversal works because movement cost between rooms is uniform (one time unit per move). The main adjustment is handling waiting time when the next room is locked until a certain timestamp. The algorithm iterates through four directions for each cell and updates the earliest reachable time. Space is used for the queue and a matrix storing the minimum time discovered so far.
Approach 2: Dijkstra's Algorithm with Min Heap (Time: O(m * n log(m * n)), Space: O(m * n))
A more robust solution treats the grid as a weighted graph and applies shortest path computation using Dijkstra’s algorithm. Each cell is a node, and the cost of moving depends on both the travel step (1 unit) and any waiting time required by the destination cell. A min heap (priority queue) always processes the cell with the smallest current time first.
When expanding a node, you compute the tentative arrival time for each neighbor. If the neighbor requires a later entry time, the algorithm waits until that timestamp before pushing it into the heap. The distance matrix stores the best known arrival time for every cell, preventing worse paths from being processed again. This method naturally handles varying arrival constraints and guarantees the optimal path.
The use of a priority queue from heap-based data structures ensures the next explored state always has the minimum time cost. This pattern appears frequently in grid-based shortest path problems and is reliable even when waiting times or dynamic costs exist.
Recommended for interviews: Dijkstra’s algorithm is the expected solution. It demonstrates understanding of shortest path problems on weighted graphs and proper use of a priority queue. Implementing the BFS-style exploration first can help clarify the traversal logic, but the heap-based Dijkstra approach is the most general and interview-ready solution.
This approach uses BFS to explore the grid starting from the top-left corner (0,0). We utilize a queue to manage current positions and a time tracking mechanism to monitor the minimum time needed to move to each adjacent room. We proceed only if moving is allowed by the given time constraints.
The code uses a deque for BFS traversal of the grid. It starts from the (0,0) room, considering movement directions (right, down, left, up). Each move's time is evaluated against the threshold specified in moveTime. If moving to a cell at any moment is permissible (max(current_time + 1, moveTime[new_x][new_y])), it's added to the queue. The loop exits when the bottom-right corner is reached.
Python
JavaScript
The time complexity is O(n * m) as each room is processed once and can potentially be added to the queue. The space complexity is also O(n * m) due to the data structures (deque and set) used to keep track of explored positions.
We employ a modified Dijkstra's algorithm to find the shortest path. Dijkstra's typically finds the shortest path with minimum weights; here, we adapt it to find the earliest arrival time at each room utilizing a priority queue to guide selections by arrival time. This helps prioritize paths that meet time constraints optimally.
This Java solution deploys Dijkstra's algorithm with a priority queue managing room nodes ordered by time of arrival. This ensures rooms are processed earliest to latest possible visit time derived from their moveTime values. Once the last room is reached, the accumulated time provides the minimum time as defined by the problem.
The time complexity is O(n * m log(n * m)) due to priority queue operations for n*m nodes. The space complexity is O(n * m) because of the data structures (queue, visited array) used.
We define a two-dimensional array dist, where dist[i][j] represents the minimum time required to reach room (i, j) from the starting point. Initially, we set all elements in the dist array to infinity, and then set the dist value of the starting point (0, 0) to 0.
We use a priority queue pq to store each state, where each state consists of three values (d, i, j), representing the time d required to reach room (i, j) from the starting point. Initially, we add the starting point (0, 0, 0) to pq.
In each iteration, we take the front element (d, i, j) from pq. If (i, j) is the endpoint, we return d. If d is greater than dist[i][j], we skip this state. Otherwise, we enumerate the four adjacent positions (x, y) of (i, j). If (x, y) is within the map, we calculate the final time t from (i, j) to (x, y) as t = max(moveTime[x][y], dist[i][j]) + 1. If t is less than dist[x][y], we update the value of dist[x][y] and add (t, x, y) to pq.
The time complexity is O(n times m times log (n times m)), and the space complexity is O(n times m). Here, n and m are the number of rows and columns of the map, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | The time complexity is O(n * m) as each room is processed once and can potentially be added to the queue. The space complexity is also O(n * m) due to the data structures (deque and set) used to keep track of explored positions. |
| Dijkstra's Algorithm Approach | The time complexity is O(n * m log(n * m)) due to priority queue operations for n*m nodes. The space complexity is O(n * m) because of the data structures (queue, visited array) used. |
| Dijkstra's Algorithm | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(m * n) | O(m * n) | Works when movement cost is uniform and only waiting adjustments are needed |
| Dijkstra's Algorithm with Min Heap | O(m * n log(m * n)) | O(m * n) | Best general solution for grid shortest path with time constraints |
Find Minimum Time to Reach Last Room I | Detailed Explanation | Leetcode 3341 | codestorywithMIK • codestorywithMIK • 12,253 views views
Watch 9 more video solutions →Practice Find Minimum Time to Reach Last Room I with our built-in code editor and test cases.
Practice on FleetCode