Find Minimum Time to Reach Last Room I solution and explanation
Google
9 more videos on this problem
Find Minimum Time to Reach Last Room I | Detailed Explanation | Leetcode 3341 | codestorywithMIKcodestorywithMIK · 37:30 · 12K views
Find Minimum Time to Reach Last Room 1 & 2 | Leetcode 3341 and 3342Techdose · 20:02 · 8K views
Daily Leetcode #1863: May 07, 2025 - 3341. Find Minimum Time to Reach Last Room IProgramming Live with Larry · 8:50 · 1K views
3341. Find Minimum Time to Reach Last Room I (Leetcode Medium)Programming Live with Larry · 13:19 · 842 views
Leetcode Weekly Contest 422 | 3341. Find Minimum Time to Reach Last Room I | Dijkstra | CodeFodCodeFod · 18:06 · 718 views
3341. Find Minimum Time to Reach Last Room I | Leetcode Daily - PythonLeetcode Daily · 7:56 · 698 views
3341. Find Minimum Time to Reach Last Room I | Dijkstra's Algorithm | LeetcodeRapid Syntax · 21:31 · 550 views
Find Minimum Time to Reach Last Room I - Leetcode 3341 - PythonTim Huang · 7:15 · 388 views
Leetcode 3341: Find Minimum Time to Reach Last Room IAlgorithms Casts · 11:09 · 380 views
Find Minimum Time to Reach Last Room I | LeetCode 3341 | Dijkstra | Java Code | Developer CodeDeveloper Coder · 28:03 · 353 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 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.
- 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 one second.
Example 2:
Input: moveTime = [[0,0,0],[0,0,0]]
Output: 3
Explanation:
The minimum time required is 3 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 one second. - At time
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] <= 109
Approach overview
Problem 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 1: Breadth-First Search (BFS) Approach
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.
from collections import deque
def minTimeToReachEnd(moveTime):
n, m = len(moveTime), len(moveTime[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
queue = deque([(0, 0, 0)]) # (x, y, time)
visited = set((0, 0))
while queue:
x, y, t = queue.popleft()
# If reached bottom-right corner
if x == n - 1 and y == m - 1:
return t
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and (nx, ny) not in visited:
nextTime = max(t + 1, moveTime[nx][ny])
queue.append((nx, ny, nextTime))
visited.add((nx, ny))
return -1
# Example usage
print(minTimeToReachEnd([[0, 4], [4, 4]])) # Output: 6
print(minTimeToReachEnd([[0, 0, 0], [0, 0, 0]])) # Output: 3function minTimeToReachEnd(moveTime) {
const directions = [[1, 0], [0, 1], [-1, 0], [0, -1]];
const n = moveTime.length;
const m = moveTime[0].length;
const queue = [{ x: 0, y: 0, t: 0 }];
const visited = new Set('0#0');
while (queue.length) {
const { x, y, t } = queue.shift();
if (x === n - 1 && y === m - 1) return t;
for (const [dx, dy] of directions) {
const nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited.has(`${nx}#${ny}`)) {
const nextTime = Math.max(t + 1, moveTime[nx][ny]);
queue.push({ x: nx, y: ny, t: nextTime });
visited.add(`${nx}#${ny}`);
}
}
}
return -1;
}
console.log(minTimeToReachEnd([[0, 4], [4, 4]])); // Output: 6
console.log(minTimeToReachEnd([[0, 0, 0], [0, 0, 0]])); // Output: 3The 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.
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.
Approach 2: Dijkstra's Algorithm Approach
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.
import java.util.*;
class MinTimeToReachEnd {
static class Node implements Comparable<Node> {
int x, y, t;
Node(int x, int y, int t) {
this.x = x; this.y = y; this.t = t;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.t, other.t);
}
}
public static int minTimeToReachEnd(int[][] moveTime) {
int n = moveTime.length, m = moveTime[0].length;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
PriorityQueue<Node> pq = new PriorityQueue<>();
boolean[][] visited = new boolean[n][m];
pq.add(new Node(0, 0, 0));
while (!pq.isEmpty()) {
Node node = pq.poll();
if (node.x == n - 1 && node.y == m - 1) return node.t;
if (visited[node.x][node.y]) continue;
visited[node.x][node.y] = true;
for (int[] d : directions) {
int nx = node.x + d[0], ny = node.y + d[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
pq.add(new Node(nx, ny, Math.max(node.t + 1, moveTime[nx][ny])));
}
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(minTimeToReachEnd(new int[][]{{0, 4}, {4, 4}})); // Output: 6
System.out.println(minTimeToReachEnd(new int[][]{{0, 0, 0}, {0, 0, 0}})); // Output: 3
}
}using System;
using System.Collections.Generic;
public class MinTimeToReachEnd {
public class Node : IComparable<Node> {
public int X, Y, Time;
public Node(int x, int y, int time) {
X = x; Y = y; Time = time;
}
public int CompareTo(Node other) {
return Time.CompareTo(other.Time);
}
}
public int MinTimeToReachEndMethod(int[][] moveTime) {
int n = moveTime.Length, m = moveTime[0].Length;
int[,] directions = new int[,] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
var pq = new SortedSet<Node>(Comparer<Node>.Create((a, b) => a.CompareTo(b)));
bool[,] visited = new bool[n, m];
pq.Add(new Node(0, 0, 0));
while (pq.Count > 0) {
var node = pq.Min;
pq.Remove(node);
if (node.X == n - 1 && node.Y == m - 1) return node.Time;
if (visited[node.X, node.Y]) continue;
visited[node.X, node.Y] = true;
for (int i = 0; i < 4; i++) {
int nx = node.X + directions[i, 0], ny = node.Y + directions[i, 1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx, ny]) {
pq.Add(new Node(nx, ny, Math.Max(node.Time + 1, moveTime[nx][ny])));
}
}
}
return -1;
}
public static void Main(string[] args) {
var solver = new MinTimeToReachEnd();
Console.WriteLine(solver.MinTimeToReachEndMethod(new int[][] {new int[] {0, 4}, new int[] {4, 4}})); // Output: 6
Console.WriteLine(solver.MinTimeToReachEndMethod(new int[][] {new int[] {0, 0, 0}, new int[] {0, 0, 0}})); // Output: 3
}
}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.
Approach 3: 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]) + 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]) + 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) + 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]) + 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 |
|---|---|
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find Minimum Time to Reach Last Room I easy or hard?
The problem is rated Medium. The main challenge is recognizing that the grid behaves like a shortest-path graph with time constraints, requiring BFS reasoning or a priority queue based Dijkstra implementation.
Find Minimum Time to Reach Last Room I Python/Java solution
Python implementations commonly use BFS with a deque to traverse the grid while adjusting arrival times. Java or C# solutions often use Dijkstra’s algorithm with a PriorityQueue or SortedSet to maintain the next cell with the smallest time.
How to solve Find Minimum Time to Reach Last Room I in O(m * n)?
An optimized BFS traversal can reach O(m * n) time if each cell is processed once while adjusting the arrival time to satisfy the room’s minimum entry requirement. The algorithm explores four directions from each cell and keeps a matrix storing the earliest reachable time.
What is the best approach for Find Minimum Time to Reach Last Room I?
Dijkstra’s algorithm with a min heap is the most reliable approach. Each grid cell is treated as a node, and the priority queue processes the cell with the smallest arrival time first. This guarantees the shortest time path while correctly handling waiting constraints imposed by each room.
Is Find Minimum Time to Reach Last Room I asked at Google/Amazon/Meta?
Grid shortest-path problems similar to this one appear frequently in interviews at companies like Google, Amazon, and Meta. Variations often require applying BFS or Dijkstra with priority queues to handle movement costs or constraints.
What data structure is used in Find Minimum Time to Reach Last Room I?
Key data structures include a queue for BFS traversal or a min heap (priority queue) for Dijkstra’s algorithm. A 2D distance matrix is also used to track the minimum time discovered for each room in the grid.
What is the time complexity of Find Minimum Time to Reach Last Room I?
The optimal Dijkstra solution runs in O(m * n log(m * n)) time because every grid cell may be inserted into a priority queue. The BFS-style traversal can run in O(m * n) when movement costs are uniform, but Dijkstra is safer for handling varying entry times.