Minimum Time to Visit a Cell In a Grid

Hard Graphs Dijkstra Original on LeetCode

Reported atAtlassian

Minimum Time to Visit a Cell In a Grid is a hard graphs problem solved with the dijkstra pattern. The best approach, optimal (dijkstra with parity-aware waiting), runs in O(m · n · log(m · n)) time and O(m · n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from simulate second by second up.

Problem

You are given an m x n grid of non-negative integers. grid[r][c] is the earliest time at which cell (r, c) may be entered: you can be on that cell only at a time t >= grid[r][c].

You start on the top-left cell (0, 0) at time 0. Every second you must move to one of the four adjacent cells (up, down, left or right); standing still is not allowed. Each move takes exactly one second.

Return the earliest time at which you can stand on the bottom-right cell (m - 1, n - 1), or -1 if it can never be reached.

Examples

Example 1

Input
grid = [[0, 1, 3, 2], [5, 1, 2, 5], [4, 3, 8, 6]]
Output
7
Why
Go (0,0) → (0,1) → (1,1) → (1,2) → (0,2) → (0,3) → (1,3) → (2,3), arriving at times 1 to 7; every cell's opening time is met on arrival.

Example 2

Input
grid = [[0, 2], [3, 1]]
Output
-1
Why
At time 1 both neighbours of the start are still closed, and you are not allowed to stand still, so you are stuck.

Example 3

Input
grid = [[0, 1], [9, 4]]
Output
4
Why
Reach (0,1) at time 1, step back to (0,0) at 2 and to (0,1) again at 3, then enter (1,1) at time 4.

Constraints

  • m == grid.length, n == grid[i].length, 2 <= m, n <= 1000, 4 <= m * n <= 10^5
  • 0 <= grid[i][j] <= 10^5
  • grid[0][0] == 0

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Simulate second by secondO(T · m · n)O(m · n)
Optimal (Dijkstra with parity-aware waiting)O(m · n · log(m · n))O(m · n)

1Simulate second by second

TimeO(T · m · n)T is the answer, which can reach about max(grid) + m + n, and each second rescans the whole grid.
SpaceO(m · n)Two boolean grids for the current and next second.

Keep the set of cells you could be standing on at time t. The set for t + 1 is every neighbour of those cells whose opening time is at most t + 1. The first t whose set contains the bottom-right cell is the answer. If the first move is impossible, answer -1 straight away; otherwise the target is always reached.

  1. If grid[0][1] > 1 and grid[1][0] > 1, return -1.
  2. cur = {(0, 0)} at t = 0.
  3. Repeat: if the target is in cur, return t; build next from neighbours with grid <= t + 1; t++.
class Solution {
    public int minimumTime(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
        int[] dr = { 1, -1, 0, 0 }, dc = { 0, 0, 1, -1 };
        boolean[][] cur = new boolean[m][n];
        cur[0][0] = true;
        for (int t = 0; ; t++) {
            if (cur[m - 1][n - 1]) return t;
            boolean[][] next = new boolean[m][n];
            for (int r = 0; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    if (!cur[r][c]) continue;
                    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 && grid[nr][nc] <= t + 1) next[nr][nc] = true;
                    }
                }
            }
            cur = next;
        }
    }
}

2Optimal (Dijkstra with parity-aware waiting)

TimeO(m · n · log(m · n))Each cell is settled once and pushes at most four heap entries.
SpaceO(m · n)The distance grid and the heap.

Once the first move is possible, waiting is always available by stepping back and forth, but only in steps of two seconds. So the earliest arrival at a neighbour from time t is t + 1 if it is already open, otherwise its opening time g when g - (t + 1) is even, or g + 1 when it is odd. Arrival times only grow along a path, so Dijkstra with a min-heap on time finds the earliest arrival at every cell.

  1. If grid[0][1] > 1 and grid[1][0] > 1, return -1.
  2. dist[0][0] = 0; push (0, 0, 0) onto a min-heap ordered by time.
  3. Pop (t, r, c); skip if stale; return t at the target.
  4. For each neighbour: nt = t + 1; if nt < g, nt = g + (g - nt) % 2. Relax dist and push.
class Solution {
    public int minimumTime(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
        int[] dr = { 1, -1, 0, 0 }, dc = { 0, 0, 1, -1 };
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        dist[0][0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.offer(new int[] { 0, 0, 0 });
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int t = cur[0], r = cur[1], c = cur[2];
            if (t > dist[r][c]) continue;
            if (r == m - 1 && c == n - 1) return t;
            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 nt = t + 1;
                if (nt < grid[nr][nc]) nt = grid[nr][nc] + (grid[nr][nc] - nt) % 2;
                if (nt < dist[nr][nc]) {
                    dist[nr][nc] = nt;
                    pq.offer(new int[] { nt, nr, nc });
                }
            }
        }
        return -1;
    }
}

Edge cases to test

  • Both neighbours of the start open later than time 1 (answer -1)
  • Waiting needed where the gap to the opening time is odd vs even (parity)
  • A 2 × 2 grid
  • All cells already open (answer is m + n - 2)

Hints

Hint 1

You can never stand still, but as soon as you have made one move you can bounce between two cells to burn time two seconds at a time.

Hint 2

So the only impossible case is when you cannot make the very first move. Otherwise every cell is reachable.

Hint 3

Run Dijkstra on arrival times. To enter a neighbour at time t + 1 that opens at g > t + 1, you arrive at g if g - (t + 1) is even, and at g + 1 if it is odd.

FAQ

What is the best time complexity for Minimum Time to Visit a Cell In a Grid?

Optimal (Dijkstra with parity-aware waiting) runs in O(m · n · log(m · n)) time and O(m · n) extra space. Each cell is settled once and pushes at most four heap entries.

Which pattern does Minimum Time to Visit a Cell In a Grid use?

It is a graphs problem that uses the dijkstra pattern. Other problems with the same pattern: Network Delay Time, Find the City With the Smallest Number of Neighbors at a Threshold Distance, Cheapest Flights Within K Stops.

Is there a brute force solution for Minimum Time to Visit a Cell In a Grid?

Yes. Simulate second by second takes O(T · m · n) time and O(m · n) space. Keep the set of cells you could be standing on at time t.

Which edge cases should I test for Minimum Time to Visit a Cell In a Grid?

Both neighbours of the start open later than time 1 (answer -1); Waiting needed where the gap to the opening time is odd vs even (parity); A 2 × 2 grid; All cells already open (answer is m + n - 2).