Find Minimum Time to Reach Last Room I

Medium
1726.

Find Minimum Time to Reach Last Room I

Find Minimum Time to Reach Last Room I is a medium coding problem on arrays, matrix and graph, asked in Amazon and Google interviews.

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 <= 50
  • 2 <= m == moveTime[i].length <= 50
  • 0 <= moveTime[i][j] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} moveTime
 * @return {number}
 */
var minTimeToReach = function(moveTime) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 50
  • 2 <= m == moveTime[i].length <= 50
  • 0 <= moveTime[i][j] <= 10^9

Hints for Find Minimum Time to Reach Last Room I

  1. Hint 1

    If you reach a room at time t, the earliest you can arrive in a neighbour is max(t, moveTime[neighbour]) + 1 — waiting never hurts.

  2. 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.

  3. Hint 3

    Run Dijkstra from (0, 0) with the arrival time as the distance, relaxing each neighbour with max(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

  1. Set time[0][0] = 0 and push it onto a min-heap.
  2. Pop the room with the smallest time t; skip it if a smaller time was already recorded.
  3. For each neighbour v, compute max(t, moveTime[v]) + 1 and relax it.
  4. 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

  • moveTime limits when you start moving into a room, so the arrival is max(t, moveTime) + 1, not max(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 -1

Java

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