Minimum Time to Visit a Cell In a Grid — Hard Problem & Solution

grid[row][col] is the earliest second at which you may step onto that cell.

Difficulty: Hard
Topics: Arrays, Matrix, Breadth-First Search, Heap, Graph, Shortest Path
Asked at: Amazon, Google, Microsoft
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

grid[row][col] is the earliest second at which you may step onto that cell. You start at the top-left cell at second 0, and each move to an adjacent cell — up, down, left or right — takes exactly one second.

Return the minimum second at which you can reach the bottom-right cell, or -1 if it cannot be reached.

Example 1

Input: grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
Output: 7

Example 2

Input: grid = [[0,2,4],[3,2,1],[1,0,4]]
Output: -1
Explanation: Both cells next to the start open too late to ever be entered.

Example 3

Input: grid = [[0,1],[1,2]]
Output: 2

Constraints

m == grid.length
n == grid[i].length
2 <= m, n <= 100
0 <= grid[i][j] <= 10^5
grid[0][0] == 0

How to solve Minimum Time to Visit a Cell In a Grid

Dijkstra's algorithm over cells, where the cost of entering a cell is max(now + 1, its opening time) — corrected upward by one if the parity is wrong, because waiting is only possible in units of two seconds.

Approach

If grid[0][1] > 1 and grid[1][0] > 1, the first move is impossible — return -1.
Otherwise run Dijkstra from the start with time 0.
Entering a neighbour: t = now + 1; if the cell opens later, jump t to the opening time and add 1 when t - (now + 1) is odd.
Return the time at which the bottom-right cell is finalised.

Why it works

Waiting is done by stepping to a neighbour and back, which always costs two seconds, so the set of times a given cell can be entered is fixed modulo 2 — that parity correction is the whole trick. Once the first move is possible, every cell is reachable, so -1 can only come from the initial check.

Complexity

Time — O(m · n · log(m · n))
Space — O(m · n)

Pitfalls

Ignoring parity gives answers one second too small.
The -1 case is decided entirely by the two cells beside the start.
A stale heap entry — one whose time has since improved — must be skipped.

Reference solution

Python

from typing import List
import heapq

def minimumTime(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    if grid[0][1] > 1 and grid[1][0] > 1:
        return -1
    BIG = float('inf')
    dist = [[BIG] * n for _ in range(m)]
    dist[0][0] = 0
    heap = [(0, 0, 0)]
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while heap:
        time, r, c = heapq.heappop(heap)
        if time > dist[r][c]:
            continue
        if r == m - 1 and c == n - 1:
            return time
        for di, dj in dirs:
            nr, nc = r + di, c + dj
            if not (0 <= nr < m and 0 <= nc < n):
                continue
            t = time + 1
            if grid[nr][nc] > t:
                t = grid[nr][nc]
                if (t - (time + 1)) % 2 != 0:
                    t += 1
            if t < dist[nr][nc]:
                dist[nr][nc] = t
                heapq.heappush(heap, (t, nr, nc))
    return -1

JavaScript

var minimumTime = function(grid) {
    var m = grid.length, n = grid[0].length, i;
    if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
    var BIG = 2000000000;
    var dist = [];
    for (i = 0; i < m * n; i++) dist.push(BIG);
    // Heap keys are time * 10000 + cell; m * n <= 10000 keeps that exact.
    var heap = [];
    var push = function(v) {
        heap.push(v);
        var k = heap.length - 1;
        while (k > 0) {
            var p = (k - 1) >> 1;
            if (heap[p] <= heap[k]) break;
            var t = heap[p]; heap[p] = heap[k]; heap[k] = t;
            k = p;
        }
    };
    var pop = function() {
        var top = heap[0];
        var last = heap.pop();
        if (heap.length > 0) {
            heap[0] = last;
            var k = 0;
            for (;;) {
                var l = 2 * k + 1, r = l + 1, s = k;
                if (l < heap.length && heap[l] < heap[s]) s = l;
                if (r < heap.length && heap[r] < heap[s]) s = r;
                if (s === k) break;
                var t = heap[s]; heap[s] = heap[k]; heap[k] = t;
                k = s;
            }
        }
        return top;
    };
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    dist[0] = 0;
    push(0);
    while (heap.length > 0) {
        var key = pop();
        var time = Math.floor(key / 10000);
        var cell = key % 10000;
        if (time > dist[cell]) continue;
        var cr = Math.floor(cell / n), cc = cell % n;
        if (cr === m - 1 && cc === n - 1) return time;
        for (var k2 = 0; k2 < 4; k2++) {
            var nr = cr + dr[k2], nc = cc + dc[k2];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            var t2 = time + 1;
            if (grid[nr][nc] > t2) {
                t2 = grid[nr][nc];
                if ((t2 - (time + 1)) % 2 !== 0) t2++;
            }
            var v = nr * n + nc;
            if (t2 >= dist[v]) continue;
            dist[v] = t2;
            push(t2 * 10000 + v);
        }
    }
    return -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue