Watch 10 video solutions for Find Minimum Time to Reach Last Room I, a medium level problem involving Array, Graph, Heap (Priority Queue). This walkthrough by codestorywithMIK has 12,253 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |