Find Minimum Time to Reach Last Room I — Problem & Solution
Find Minimum Time to Reach Last Room I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find Minimum Time to Reach Last Room I is a medium coding problem on arrays, matrix and graph, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Matrix, Graph, Heap, Shortest Path
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A dungeon has n x m rooms laid out as a grid. moveTime[i][j] is the earliest second at which you may start moving into room (i, j).
You are in room (0, 0) at time t = 0. Moving between two rooms that share a wall takes exactly one second, and you may wait in a room as long as you like.
Return the minimum time at which you can arrive in room (n - 1, m - 1).
Example 1
Input: moveTime = [[0,4],[4,4]]
Output: 6
Explanation: Wait until t = 4, move to (1,0) arriving at 5, then move to (1,1) arriving at 6.
Example 2
Input: moveTime = [[0,0,0],[0,0,0]]
Output: 3
Explanation: No waiting is needed: three moves along any shortest route.
Example 3
Input: moveTime = [[0,1],[1,2]]
Output: 3
Constraints
2 <= n == moveTime.length <= 502 <= m == moveTime[i].length <= 500 <= moveTime[i][j] <= 10^9
Hints for Find Minimum Time to Reach Last Room I
Hint 1
If you reach a room at time
t, the earliest you can arrive in a neighbour ismax(t, moveTime[neighbour]) + 1— waiting never hurts.Hint 2
Arriving earlier is never worse, so this is a shortest-path problem where each edge's cost depends on the time you start it — but it is still monotone in the start time.
Hint 3
Run Dijkstra from
(0, 0)with the arrival time as the distance, relaxing each neighbour withmax(t, moveTime) + 1.
How to solve Find Minimum Time to Reach Last Room I
Earliest arrival times obey Dijkstra's rule: the transition t → max(t, moveTime[v]) + 1 never decreases and never gets worse for a smaller t, so the room popped with the smallest time is final.
Approach
- Set
time[0][0] = 0and push it onto a min-heap. - Pop the room with the smallest time
t; skip it if a smaller time was already recorded. - For each neighbour
v, computemax(t, moveTime[v]) + 1and relax it. - Stop when the bottom-right room is popped and return its time.
Why it works
The arrival function is non-decreasing in the departure time and always adds at least one second, which is exactly what Dijkstra's correctness proof needs: once the smallest tentative time is popped, no other route can reach that room sooner.
Complexity
- Time —
O(n · m · log(n · m)) - Space —
O(n · m)
Pitfalls
moveTimelimits when you start moving into a room, so the arrival ismax(t, moveTime) + 1, notmax(t + 1, moveTime).- Times reach about 10^9, so a packed heap key needs 64 bits.
- A plain BFS by step count ignores waiting and gives wrong answers.
Reference solution
Python
from typing import List
import heapq
def minTimeToReach(moveTime: List[List[int]]) -> int:
n, m = len(moveTime), len(moveTime[0])
INF = float("inf")
dist = [[INF] * m for _ in range(n)]
dist[0][0] = 0
heap = [(0, 0, 0)]
while heap:
t, r, c = heapq.heappop(heap)
if t > dist[r][c]:
continue
if r == n - 1 and c == m - 1:
return t
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < m:
nt = max(t, moveTime[nr][nc]) + 1
if nt < dist[nr][nc]:
dist[nr][nc] = nt
heapq.heappush(heap, (nt, nr, nc))
return -1Java
public static int minTimeToReach(int[][] moveTime) {
int n = moveTime.length, m = moveTime[0].length, total = n * m;
final long SH = 1048576L;
int[] DR = {1, -1, 0, 0}, DC = {0, 0, 1, -1};
long[] dist = new long[total];
Arrays.fill(dist, Long.MAX_VALUE);
dist[0] = 0;
PriorityQueue<Long> heap = new PriorityQueue<>();
heap.add(0L);
while (!heap.isEmpty()) {
long key = heap.poll();
int idx = (int) (key % SH);
long t = key / SH;
if (t > dist[idx]) continue;
if (idx == total - 1) return (int) t;
int r = idx / m, c = idx % m;
for (int d = 0; d < 4; d++) {
int nr = r + DR[d], nc = c + DC[d];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
long nt = Math.max(t, (long) moveTime[nr][nc]) + 1;
int ni = nr * m + nc;
if (nt < dist[ni]) { dist[ni] = nt; heap.add(nt * SH + ni); }
}
}
return -1;
}C++
int minTimeToReach(vector<vector<int>>& moveTime) {
int n = moveTime.size(), m = moveTime[0].size();
int DR[4] = {1, -1, 0, 0}, DC[4] = {0, 0, 1, -1};
vector<long long> dist(n * m, LLONG_MAX);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> heap;
dist[0] = 0;
heap.push(make_pair(0LL, 0));
while (!heap.empty()) {
long long t = heap.top().first;
int idx = heap.top().second;
heap.pop();
if (t > dist[idx]) continue;
if (idx == n * m - 1) return (int) t;
int r = idx / m, c = idx % m;
for (int d = 0; d < 4; d++) {
int nr = r + DR[d], nc = c + DC[d];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
long long nt = max(t, (long long) moveTime[nr][nc]) + 1;
int ni = nr * m + nc;
if (nt < dist[ni]) { dist[ni] = nt; heap.push(make_pair(nt, ni)); }
}
}
return -1;
}JavaScript
var minTimeToReach = function(moveTime) {
var n = moveTime.length, m = moveTime[0].length, total = n * m, SH = 1048576;
var DR = [1, -1, 0, 0], DC = [0, 0, 1, -1];
var dist = [];
for (var i = 0; i < total; i++) dist.push(4e12);
dist[0] = 0;
var heap = [0];
while (heap.length > 0) {
var key = heapPop(heap);
var idx = key % SH, t = (key - idx) / SH;
if (t > dist[idx]) continue;
if (idx === total - 1) return t;
var r = Math.floor(idx / m), c = idx % m;
for (var d = 0; d < 4; d++) {
var nr = r + DR[d], nc = c + DC[d];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
var nt = Math.max(t, moveTime[nr][nc]) + 1, ni = nr * m + nc;
if (nt < dist[ni]) { dist[ni] = nt; heapPush(heap, nt * SH + ni); }
}
}
return -1;
};
var heapPush = function(h, v) {
h.push(v);
var i = h.length - 1;
while (i > 0) {
var p = (i - 1) >> 1;
if (h[p] <= h[i]) break;
var t = h[p]; h[p] = h[i]; h[i] = t;
i = p;
}
};
var heapPop = function(h) {
var top = h[0];
var last = h.pop();
if (h.length > 0) {
h[0] = last;
var j = 0;
for (;;) {
var l = 2 * j + 1, r = l + 1, s = j;
if (l < h.length && h[l] < h[s]) s = l;
if (r < h.length && h[r] < h[s]) s = r;
if (s === j) break;
var t = h[s]; h[s] = h[j]; h[j] = t;
j = s;
}
}
return top;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal