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 one second for one move and two seconds for the next, alternating between the two.
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: 7
Explanation:
The minimum time required is 7 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 two seconds.Example 2:
Input: moveTime = [[0,0,0,0],[0,0,0,0]]
Output: 6
Explanation:
The minimum time required is 6 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 two seconds.t == 3, move from room (1, 1) to room (1, 2) in one second.t == 4, move from room (1, 2) to room (1, 3) in two seconds.Example 3:
Input: moveTime = [[0,1],[1,2]]
Output: 4
Constraints:
2 <= n == moveTime.length <= 7502 <= m == moveTime[i].length <= 7500 <= moveTime[i][j] <= 109Problem Overview: You are given a grid where each cell represents a room and the value indicates the earliest time you are allowed to enter it. Starting from the top‑left room, the goal is to reach the bottom‑right room in the minimum possible time while respecting each room’s time constraint.
Approach 1: Dijkstra's Algorithm (Time: O(mn log(mn)), Space: O(mn))
This problem behaves like a weighted shortest path problem on a grid. Each room is a node, and moving to a neighbor takes time while also respecting the earliest entry time of that room. Use a graph model where edges connect adjacent cells. A priority queue always expands the room with the smallest arrival time. When moving to a neighbor, compute the earliest valid arrival time: if the room is locked until a later time, you must wait before entering. This approach guarantees the optimal path because Dijkstra always processes the smallest known distance first.
Approach 2: Dijkstra's Algorithm for Grid (Time: O(mn log(mn)), Space: O(mn))
This is a grid‑optimized version of the previous idea. Instead of explicitly building a graph, treat each cell directly as a node and explore the four directions (up, down, left, right). Maintain a distance matrix storing the earliest time each cell can be reached. Push states into a min‑heap and relax neighbors just like standard shortest path problems. The key step is adjusting arrival time to satisfy the room’s opening constraint before pushing it to the heap.
Approach 3: Dynamic Programming (Time: O(mn), Space: O(mn))
A dynamic programming approach attempts to propagate the earliest reachable time through the grid. For each cell, compute the minimum arrival time based on previously processed neighbors while respecting the cell’s availability constraint. This works best when transitions follow a predictable order, but because movement can occur in multiple directions, updates may need to be revisited. In practice, DP alone becomes tricky for general shortest path scenarios but still provides intuition about how time constraints propagate across the grid.
Approach 4: Dynamic Programming with Breadth‑First Search (Time: O(mn), Space: O(mn))
This hybrid approach combines BFS traversal with DP‑style state updates. BFS explores reachable cells layer by layer while maintaining the earliest arrival time for each room. If reaching a neighbor requires waiting due to its time constraint, the algorithm updates the state and reprocesses it when a better arrival time appears. This reduces redundant exploration compared to naive BFS but still tracks time states carefully.
Recommended for interviews: Dijkstra’s algorithm is the expected solution. The grid naturally forms a weighted graph where each transition may include waiting time, making a priority queue approach the most reliable. Explaining the brute reasoning first and then modeling the grid as a shortest path problem demonstrates strong problem‑solving and graph fundamentals.
Dijkstra's Algorithm can help find the shortest path in a graph, checking each path's cost in terms of time rather than distance. We treat each room as a node, with edges representing the time it takes to traverse from one node to another (alternating between 1 and 2 seconds). We can use a priority queue to efficiently get the room with the minimum current time cost.
This implementation uses a priority queue to simulate Dijkstra's algorithm. It starts from room (0,0) and explores neighboring rooms with alternating movement times. For each room, it calculates the next possible movement time, checks the constraint with moveTime, and updates with the shortest known time if possible, iterating until it reaches the goal room. If it reaches the end, it returns the current time; otherwise, it continues exploring. The end condition helps in returning the minimum time as updates are based on the earliest time of availability and reachability.
Python
Both time and space complexity are O(n*m*log(n*m)) due to the priority queue operations for all rooms.
A dynamic programming approach builds a 2D array of size n x m to store the minimum time to reach each room. Starting from (0,0), iterate over each room, calculating the minimum time needed to reach its adjacent rooms with alternating movement times. This approach leverages dynamic properties, updating reachable rooms based on the prior values in the grid plus the movement costs.
This solution uses a 2D dp array to compute the minimum time required to reach each room. Starting from the first room, it iterates through each room (i, j), calculating the minimum time for its adjacent cells based on the current time and alternating increment. The time calculation considers whether an extra second is needed, based on the alternating pattern. It returns the value at the bottom right corner of the dp table.
Java
This approach runs in O(n*m) time due to the need to iterate through each cell. The space complexity is O(n*m) because of the dp table.
Using Dijkstra's algorithm is suitable for this problem as it involves finding the shortest path on a weighted graph. Here, the grid can be transformed into a graph where each cell is a node, and edges exist between adjacent cells with weights alternating between 1 and 2 seconds. With moveTime constraints at each cell, we maintain the earliest possible time we can reach each cell, ensuring compliance with these conditions.
This implementation of Dijkstra's algorithm uses a priority queue to explore the shortest paths to each cell efficiently. Every time a new cell is considered, the algorithm checks if moving to that cell is feasible given the constraints in the moveTime matrix. By maintaining a dynamic list via a priority queue, we ensure that we explore the minimum required time paths first, efficiently finding the least time path to the bottom-right corner.
Python
The time complexity is O(n * m * log(n * m)), where n is the number of rows and m is the number of columns, due to the priority queue operations. The space complexity is O(n * m) for storing the minimum times and the queue.
This approach utilizes breadth-first search (BFS), treating move times as conditions while propagating the earliest possible time one can enter each room. Each cell is monitored for the minimum time that satisfies the given moveTime constraint, essentially treating move times as a boundary condition we expand upon.
This solution arranges a BFS traversal alongside a DP table to retain the minimum time for reaching each cell. The traversal leverages a queue to explore neighboring cells in layers based on the constraints provided by moveTime. The key is to maintain updated and valid timings ensuring compliance with the staggered move durations, naturally accommodating the alternating time costs on movements.
Java
The time complexity is O(n * m), as every cell is visited once in order to update times. The space complexity is also O(n * m) due to the storage of minimum times and queue operations.
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]) + (i + j) bmod 2 + 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 |
|---|---|
| Approach using Dijkstra's Algorithm | Both time and space complexity are O(n*m*log(n*m)) due to the priority queue operations for all rooms. |
| Dynamic Programming Approach | This approach runs in O(n*m) time due to the need to iterate through each cell. The space complexity is O(n*m) because of the dp table. |
| Dijkstra's Algorithm for Grid | The time complexity is O(n * m * log(n * m)), where n is the number of rows and m is the number of columns, due to the priority queue operations. The space complexity is O(n * m) for storing the minimum times and the queue. |
| Dynamic Programming with Breadth-First Search | The time complexity is O(n * m), as every cell is visited once in order to update times. The space complexity is also O(n * m) due to the storage of minimum times and queue operations. |
| Dijkstra's Algorithm | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra's Algorithm | O(mn log(mn)) | O(mn) | General case where rooms have different earliest entry times |
| Grid‑Optimized Dijkstra | O(mn log(mn)) | O(mn) | Most practical solution for matrix shortest path problems |
| Dynamic Programming | O(mn) | O(mn) | When movement directions are restricted or predictable |
| DP with BFS | O(mn) | O(mn) | When exploring grid states incrementally with time propagation |
Find Minimum Time to Reach Last Room 1 & 2 | Leetcode 3341 and 3342 • Techdose • 8,047 views views
Watch 9 more video solutions →Practice Find Minimum Time to Reach Last Room II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor