Minimum Time to Visit a Cell In a Grid

Hard
957.

Minimum Time to Visit a Cell In a Grid

Minimum Time to Visit a Cell In a Grid is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google, Microsoft and Atlassian interviews.

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
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[][]} grid
 * @return {number}
 */
var minimumTime = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Minimum Time to Visit a Cell In a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Time to Visit a Cell In a Grid is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google, Microsoft and Atlassian interviews.

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

Hints for Minimum Time to Visit a Cell In a Grid

  1. Hint 1

    If both cells next to the start open later than second 1, you can never take a first step.

  2. Hint 2

    Otherwise you can always waste time by stepping back and forth — but each round trip costs two seconds.

  3. Hint 3

    So arrival times have a fixed parity per cell; run Dijkstra's algorithm with that adjustment.

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

  1. If grid[0][1] > 1 and grid[1][0] > 1, the first move is impossible — return -1.
  2. Otherwise run Dijkstra from the start with time 0.
  3. 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.
  4. 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

Java

public static int minimumTime(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
    final int BIG = Integer.MAX_VALUE;
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, BIG);
    dist[0][0] = 0;
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    heap.add(new int[] { 0, 0, 0 });
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    while (!heap.isEmpty()) {
        int[] cur = heap.poll();
        int time = cur[0], r = cur[1], c = cur[2];
        if (time > dist[r][c]) continue;
        if (r == m - 1 && c == n - 1) return time;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int t = time + 1;
            if (grid[nr][nc] > t) {
                t = grid[nr][nc];
                if ((t - (time + 1)) % 2 != 0) t++;
            }
            if (t < dist[nr][nc]) {
                dist[nr][nc] = t;
                heap.add(new int[] { t, nr, nc });
            }
        }
    }
    return -1;
}

C++

int minimumTime(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
    const int BIG = 2000000000;
    vector<vector<int>> dist(m, vector<int>(n, BIG));
    dist[0][0] = 0;
    priority_queue<array<int,3>, vector<array<int,3>>, greater<array<int,3>>> heap;
    heap.push({ 0, 0, 0 });
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    while (!heap.empty()) {
        auto cur = heap.top();
        heap.pop();
        int time = cur[0], r = cur[1], c = cur[2];
        if (time > dist[r][c]) continue;
        if (r == m - 1 && c == n - 1) return time;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int t = time + 1;
            if (grid[nr][nc] > t) {
                t = grid[nr][nc];
                if ((t - (time + 1)) % 2 != 0) t++;
            }
            if (t < dist[nr][nc]) {
                dist[nr][nc] = t;
                heap.push({ 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal