Find Minimum Time to Reach Last Room II solution and explanation
Google
9 more videos on this problem
Find Minimum Time to Reach Last Room 1 & 2 | Leetcode 3341 and 3342Techdose · 20:02 · 8K views
Find Minimum Time to Reach Last Room II | Using Same Code | Leetcode 3342 | codestorywithMIKcodestorywithMIK · 18:39 · 6K views
Daily Leetcode #1864: May 08, 2025 - 3342. Find Minimum Time to Reach Last Room IIProgramming Live with Larry · 9:05 · 356 views
3342. Find Minimum Time to Reach Last Room II | Leetcode Daily - PythonLeetcode Daily · 10:29 · 339 views
3342. Find Minimum Time to Reach Last Room II (Leetcode Medium)Programming Live with Larry · 14:19 · 335 views
Find Minimum Time to Reach Last Room II - Leetcode 3342 - PythonTim Huang · 8:38 · 273 views
Leetcode 3342: Find Minimum Time to Reach Last Room IIAlgorithms Casts · 10:04 · 200 views
3342. Find Minimum Time to Reach Last Room II | Dijkstra's Algorithm | LeetcodeRapid Syntax · 9:26 · 166 views
Leetcode Weekly Contest 422 | 3342. Find Minimum Time to Reach Last Room II | Dijkstra | CodeFodCodeFod · 14:53 · 148 views
Leetcode 3342 | Find Minimum Time to Reach Last Room II | Weekly Contest 422Road To FAANG · 6:46 · 145 views
The problem
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.
- At time
t == 4, move from room(0, 0)to room(1, 0)in one second. - At time
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.
- At time
t == 0, move from room(0, 0)to room(1, 0)in one second. - At time
t == 1, move from room(1, 0)to room(1, 1)in two seconds. - At time
t == 3, move from room(1, 1)to room(1, 2)in one second. - At time
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] <= 109
Approach overview
Problem 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.
Approach 1: Approach using Dijkstra's Algorithm
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.
import heapq
def min_time_to_reach_last_room(moveTime):
n, m = len(moveTime), len(moveTime[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
visited = [[float('inf')] * m for _ in range(n)]
visited[0][0] = 0
pq = [(0, 0, 0)] # time, row, col
while pq:
time, x, y = heapq.heappop(pq)
if (x, y) == (n - 1, m - 1):
return time
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m:
new_time = time + (1 if (time % 3 != 2) else 2)
if new_time >= moveTime[nx][ny] and new_time < visited[nx][ny]:
visited[nx][ny] = new_time
heapq.heappush(pq, (new_time, nx, ny))
return -1This 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.
Both time and space complexity are O(n*m*log(n*m)) due to the priority queue operations for all rooms.
Approach 2: Dynamic Programming Approach
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.
public class Solution {
public int minTimeToReachLastRoom(int[][] moveTime) {
int n = moveTime.length, m = moveTime[0].length;
int[][] dp = new int[n][m];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int time = dp[i][j];
if (i + 1 < n) dp[i + 1][j] = Math.min(dp[i + 1][j], Math.max(moveTime[i + 1][j], time + 1 + ((time % 3 == 2) ? 1 : 0)));
if (j + 1 < m) dp[i][j + 1] = Math.min(dp[i][j + 1], Math.max(moveTime[i][j + 1], time + 1 + ((time % 3 == 2) ? 1 : 0)));
}
}
return dp[n - 1][m - 1];
}
}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.
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.
Approach 3: Dijkstra's Algorithm for Grid
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.
import heapq
def minTimeToReachLastRoom(moveTime):
n, m = len(moveTime), len(moveTime[0])
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
pq = [(0, 0, 0)] # (current_time, x, y)
min_time = [[float('inf')] * m for _ in range(n)]
min_time[0][0] = 0
while pq:
current_time, x, y = heapq.heappop(pq)
if (x, y) == (n - 1, m - 1):
return current_time
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m:
arrival_time = max(moveTime[nx][ny], current_time + 1)
if (arrival_time - current_time) % 2 == 1: # 1 second move
new_time = arrival_time + 1
else: # 2 seconds move
new_time = arrival_time + 2
if new_time < min_time[nx][ny]:
min_time[nx][ny] = new_time
heapq.heappush(pq, (new_time, nx, ny))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.
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.
Approach 4: Dynamic Programming with Breadth-First Search
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.
import java.util.*;
class Solution {
public int minTimeToReachLastRoom(int[][] moveTime) {
int n = moveTime.length, m = moveTime[0].length;
int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int[][] minTime = new int[n][m];
for (int[] row : minTime) {
Arrays.fill(row, Integer.MAX_VALUE);
}
minTime[0][0] = 0;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0, 0}); // {current_time, x, y}
while (!queue.isEmpty()) {
int[] current = queue.poll();
int currentTime = current[0];
int x = current[1];
int y = current[2];
for (int[] dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
int timeToEnter = Math.max(currentTime + 1, moveTime[nx][ny]);
int updateTime = (timeToEnter - currentTime) % 2 == 1 ? timeToEnter + 1 : timeToEnter + 2;
if (updateTime < minTime[nx][ny]) {
minTime[nx][ny] = updateTime;
queue.offer(new int[]{updateTime, nx, ny});
}
}
}
}
return minTime[n - 1][m - 1];
}
}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.
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.
Approach 5: Dijkstra's Algorithm
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.
class Solution {
public:
int minTimeToReach(vector<vector<int>>& moveTime) {
int n = moveTime.size();
int m = moveTime[0].size();
vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
dist[0][0] = 0;
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
pq.push({0, 0, 0});
int dirs[5] = {-1, 0, 1, 0, -1};
while (1) {
auto [d, i, j] = pq.top();
pq.pop();
if (i == n - 1 && j == m - 1) {
return d;
}
if (d > dist[i][j]) {
continue;
}
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k];
int y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < m) {
int t = max(moveTime[x][y], dist[i][j]) + (i + j) % 2 + 1;
if (dist[x][y] > t) {
dist[x][y] = t;
pq.push({t, x, y});
}
}
}
}
}
};function minTimeToReach(moveTime: number[][]): number {
const n = moveTime.length;
const m = moveTime[0].length;
const dist = Array.from({ length: n }, () => Array(m).fill(Infinity));
dist[0][0] = 0;
type Node = [number, number, number];
const pq = new PriorityQueue<Node>((a, b) => a[0] - b[0]);
pq.enqueue([0, 0, 0]);
const dirs = [-1, 0, 1, 0, -1];
while (!pq.isEmpty()) {
const [d, i, j] = pq.dequeue();
if (d > dist[i][j]) continue;
if (i === n - 1 && j === m - 1) return d;
for (let k = 0; k < 4; k++) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < m) {
const t = Math.max(moveTime[x][y], d) + ((i + j) % 2) + 1;
if (t < dist[x][y]) {
dist[x][y] = t;
pq.enqueue([t, x, y]);
}
}
}
}
return -1;
}func minTimeToReach(moveTime [][]int) int {
n, m := len(moveTime), len(moveTime[0])
dist := make([][]int, n)
for i := range dist {
dist[i] = make([]int, m)
for j := range dist[i] {
dist[i][j] = math.MaxInt32
}
}
dist[0][0] = 0
pq := &hp{}
heap.Init(pq)
heap.Push(pq, tuple{0, 0, 0})
dirs := []int{-1, 0, 1, 0, -1}
for {
p := heap.Pop(pq).(tuple)
d, i, j := p.dis, p.x, p.y
if i == n-1 && j == m-1 {
return d
}
if d > dist[i][j] {
continue
}
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < m {
t := max(moveTime[x][y], dist[i][j]) + (i+j)%2 + 1
if dist[x][y] > t {
dist[x][y] = t
heap.Push(pq, tuple{t, x, y})
}
}
}
}
}
type tuple struct{ dis, x, y int }
type hp []tuple
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() (v any) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find Minimum Time to Reach Last Room II easy or hard?
The problem is rated Medium because it requires recognizing the grid as a shortest path graph with time constraints. Implementing Dijkstra’s algorithm with correct waiting logic can be tricky, but the overall concept is standard for candidates familiar with graph traversal.
Find Minimum Time to Reach Last Room II Python/Java solution
Python solutions typically implement Dijkstra’s algorithm using heapq to maintain the priority queue. Java implementations use PriorityQueue with a custom comparator and a 2D distance array. Both versions follow the same shortest path logic with O(mn log(mn)) complexity.
How to solve Find Minimum Time to Reach Last Room II in O(mn log mn)?
Model the grid as a shortest path problem. Use a min‑heap to store states as (time, row, column). From each cell, explore four directions and compute the earliest valid time to enter the neighbor by considering its constraint value. Update the distance matrix and push the new state into the heap if the arrival time improves.
What is the best approach for Find Minimum Time to Reach Last Room II?
The best approach is Dijkstra's algorithm using a priority queue. Each grid cell is treated as a node, and the algorithm always processes the cell with the smallest arrival time. When moving to a neighbor, the arrival time must respect that room’s earliest available time, which may require waiting. This results in a time complexity of O(mn log(mn)).
Is Find Minimum Time to Reach Last Room II asked at Google/Amazon/Meta?
Grid shortest path problems with constraints frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving Dijkstra’s algorithm, priority queues, and matrix traversal are especially common because they test graph modeling and optimization skills.
What data structure is used in Find Minimum Time to Reach Last Room II?
The key data structure is a min‑heap (priority queue) used in Dijkstra’s algorithm. It ensures the next cell processed always has the smallest known arrival time. A distance matrix is also used to track the earliest time each room can be reached.
What is the time complexity of Find Minimum Time to Reach Last Room II?
The optimal solution using Dijkstra’s algorithm runs in O(mn log(mn)) time, where m and n are the grid dimensions. Each cell may be pushed into a priority queue, and heap operations cost log(mn). Space complexity is O(mn) for the distance matrix and heap storage.