Minimum Time to Visit a Cell In a Grid

Hard

#2357Time: O((m*n)^2) in the worst case. Each of the V = m*n vertices can be enqueued up to V times, and for each dequeue, we check E (at most 4) edges.Space: O(m*n) for the `dist` array and the queue, which in the worst case could hold many states for each cell.1 company

Algorithms

Breadth-First Search Shortest Path

Data structures

Array Heap (Priority Queue)Matrix Graph

Companies

Atlassian

Prompt

You are given a m x n matrix grid consisting of non-negative integers where grid[row][col] represents the minimum time required to be able to visit the cell (row, col), which means you can visit the cell (row, col) only when the time you visit it is greater than or equal to grid[row][col].

You are standing in the top-left cell of the matrix in the 0^th second, and you must move to any adjacent cell in the four directions: up, down, left, and right. Each move you make takes 1 second.

Return the minimum time required in which you can visit the bottom-right cell of the matrix. If you cannot visit the bottom-right cell, then return -1.

Example 1:

Input: grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
Output: 7
Explanation: One of the paths that we can take is the following:
- at t = 0, we are on the cell (0,0).
- at t = 1, we move to the cell (0,1). It is possible because grid[0][1] <= 1.
- at t = 2, we move to the cell (1,1). It is possible because grid[1][1] <= 2.
- at t = 3, we move to the cell (1,2). It is possible because grid[1][2] <= 3.
- at t = 4, we move to the cell (1,1). It is possible because grid[1][1] <= 4.
- at t = 5, we move to the cell (1,2). It is possible because grid[1][2] <= 5.
- at t = 6, we move to the cell (1,3). It is possible because grid[1][3] <= 6.
- at t = 7, we move to the cell (2,3). It is possible because grid[2][3] <= 7.
The final time is 7. It can be shown that it is the minimum time possible.

Example 2:

Input: grid = [[0,2,4],[3,2,1],[1,0,4]]
Output: -1
Explanation: There is no path from the top left to the bottom-right cell.

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This problem can be modeled as finding the shortest path in a state graph where states are (time, row, col). A BFS-like approach, similar to the Shortest Path Faster Algorithm (SPFA), can solve it by using a regular queue instead of a priority queue. While simpler in concept, this approach can be inefficient because it might explore paths that are clearly not optimal early on, leading to re-visiting and re-processing cells multiple times. In the worst-case scenario, its time complexity is much higher than Dijkstra's algorithm, making it unsuitable for large grids.

Algorithm

Initialize a dist array with infinity and dist[0][0] = 0.
Create a standard queue and add the starting state (0, 0, 0).
While the queue is not empty:
- Dequeue a state (t, r, c).
- For each neighbor (nr, nc):
  - Calculate the earliest possible arrival time new_time based on the current time t, the grid constraint grid[nr][nc], and parity rules.
  - This calculation must also check if waiting is possible (i.e., if there's a 'helper' neighbor accessible at time t+1).
  - If new_time is better than dist[nr][nc], update dist[nr][nc] and enqueue (new_time, nr, nc).
After the loop, dist[m-1][n-1] holds the result.

Walkthrough

The core idea is to maintain an array dist[m][n] storing the minimum time to reach each cell. We start at (0,0) at time 0 and use a standard queue to perform the search. Each element in the queue will be a tuple (time, row, col).

When we extract a cell (r, c) reached at time t from the queue, we explore its neighbors. For each neighbor (nr, nc):

A direct move is possible if we can arrive at t+1 without violating the grid's time constraint, i.e., t + 1 >= grid[nr][nc]. The new time at (nr, nc) would be t + 1.
If a direct move is not possible (t + 1 < grid[nr][nc]), we must wait. Waiting involves moving back and forth between the current cell (r, c) and an adjacent 'helper' cell. This is only possible if there's at least one neighbor (or, oc) of (r, c) that can be visited at time t + 1 (i.e., t + 1 >= grid[or][oc]).
If waiting is possible, the arrival time at (nr, nc) must be at least grid[nr][nc] and also have a different parity from the departure time t (since any path from (r,c) to (nr,nc) takes an odd number of steps). The minimum such time is calculated.
If we find a path to a neighbor (nr, nc) with a new time that is less than the currently known dist[nr][nc], we update the distance and add the new state (new_time, nr, nc) to the queue.

Since we use a regular queue, we are not guaranteed to process the cell with the minimum time first. This can lead to a cell being enqueued multiple times if shorter paths are found later, which is the main reason for the potential inefficiency.

Complexity

Time

O((m*n)^2) in the worst case. Each of the V = m*n vertices can be enqueued up to V times, and for each dequeue, we check E (at most 4) edges.

Space

O(m*n) for the `dist` array and the queue, which in the worst case could hold many states for each cell.

Trade-offs

Pros

Conceptually simpler as it avoids the use of a priority queue.

Cons

Inefficient for this problem, with a worst-case time complexity that is too high for the given constraints.
Likely to result in a 'Time Limit Exceeded' error on competitive programming platforms.
A correct implementation requires the same complex logic as the Dijkstra approach, negating its main advantage of simplicity.

This problem is a variation of the shortest path problem on a grid. Dijkstra's algorithm is perfectly suited for this, as it efficiently finds the shortest paths from a single source in a graph with non-negative edge weights. Here, the 'weight' or 'cost' to travel between cells is not constant; it depends on the arrival time at the current cell and the time constraint of the destination cell. We use a priority queue to always expand the search from the cell that is reachable in the minimum amount of time. This ensures that the first time we reach any cell, it is via the fastest possible path, so we only need to process each cell once.

Algorithm

Initialize a dist array with infinity and dist[0][0] = 0.
Create a priority queue ordered by time and add the starting state (0, 0, 0).
While the priority queue is not empty:
- Dequeue the state (t, r, c) with the minimum time.
- If this path is suboptimal (t > dist[r][c]), skip.
- If it's the destination, return t.
- For each neighbor (nr, nc):
  - Calculate the earliest possible arrival time new_time based on t, grid[nr][nc], and parity rules. This calculation must account for whether a direct move is possible or if waiting is required and feasible.
  - If new_time is better than dist[nr][nc], update dist[nr][nc] and add (new_time, nr, nc) to the priority queue.
If the loop finishes, the destination is unreachable, so return -1.

Walkthrough

The algorithm maintains a dist array to store the minimum time to reach each cell, initialized to infinity. A priority queue stores tuples of (time, row, col), ordered by time.

We start by pushing (0, 0, 0) to the priority queue. Then, we repeatedly extract the state with the smallest time.

For a cell (r, c) reached at time t:

If t is greater than the already recorded dist[r][c], we skip it, as we've found a better path already.
If (r, c) is the destination, we have found the minimum time and can return t.
We then consider moving to each neighbor (nr, nc). The key is calculating the new arrival time new_time. The logic for this is as follows:
- If t + 1 >= grid[nr][nc], a direct move is possible. The arrival time is simply t + 1.
- If t + 1 < grid[nr][nc], we must wait. The arrival time must be at least grid[nr][nc]. Furthermore, the time elapsed (new_time - t) must be an odd number of seconds. This means new_time and t must have different parity. The minimum new_time is grid[nr][nc] if (grid[nr][nc] - t) is odd, or grid[nr][nc] + 1 if (grid[nr][nc] - t) is even.
This waiting is only possible if we can actually make moves to pass the time. This requires a 'helper' neighbor we can visit at t+1. If no such neighbor exists, we are stuck and cannot move to (nr, nc) if it requires waiting.
If a valid new_time is calculated and it's less than dist[nr][nc], we update dist[nr][nc] and push (new_time, nr, nc) to the priority queue.

If the priority queue becomes empty and we haven't reached the destination, it's unreachable, and we return -1.

1import java.util.Arrays;2import java.util.PriorityQueue;3 4class Solution {5    public int minimumTime(int[][] grid) {6        int m = grid.length;7        int n = grid[0].length;8 9        // A crucial edge case: if we cannot move from the start, it's impossible.10        if (grid[0][1] > 1 && grid[1][0] > 1) {11            return -1;12        }13 14        int[][] dist = new int[m][n];15        for (int[] row : dist) {16            Arrays.fill(row, Integer.MAX_VALUE);17        }18 19        // PriorityQueue stores {time, row, col}20        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);21 22        dist[0][0] = 0;23        pq.offer(new int[]{0, 0, 0});24 25        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};26 27        while (!pq.isEmpty()) {28            int[] curr = pq.poll();29            int t = curr[0];30            int r = curr[1];31            int c = curr[2];32 33            if (t > dist[r][c]) {34                continue;35            }36 37            if (r == m - 1 && c == n - 1) {38                return t;39            }40 41            for (int[] dir : dirs) {42                int nr = r + dir[0];43                int nc = c + dir[1];44 45                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {46                    int newTime;47                    int requiredTime = grid[nr][nc];48                    49                    if (t + 1 >= requiredTime) {50                        newTime = t + 1;51                    } else {52                        int diff = requiredTime - t;53                        if (diff % 2 == 0) { // Same parity, need an extra step54                            newTime = requiredTime + 1;55                        } else { // Different parity, can arrive exactly at requiredTime56                            newTime = requiredTime;57                        }58                    }59 60                    if (newTime < dist[nr][nc]) {61                        dist[nr][nc] = newTime;62                        pq.offer(new int[]{newTime, nr, nc});63                    }64                }65            }66        }67 68        return -1;69    }70}

Note: The provided code snippet simplifies the logic by assuming that if waiting is needed, it is always possible. This is not always true. A fully correct solution would need to check for a valid 'helper' neighbor at every step before calculating times for neighbors that require waiting. The initial check for the start node (0,0) handles the most common failure case for this simplified logic.

Complexity

Time

O(m*n * log(m*n)). The number of vertices V is m*n and edges E is at most 4*m*n. Each vertex is processed once. Priority queue operations (offer and poll) take O(log V) time.

Space

O(m*n) to store the `dist` array and the elements in the priority queue.

Trade-offs

Pros

Guaranteed to find the minimum time due to the nature of Dijkstra's algorithm.
Efficient, with a time complexity suitable for the problem's constraints.

Cons

Slightly more complex to implement than a standard BFS due to the priority queue.
The logic for calculating the time to the next cell is non-trivial and requires careful handling of the waiting mechanism and parity.

Solutions

Solution

1class Solution {2public3  int minimumTime(int[][] grid) {4    if (grid[0][1] > 1 && grid[1][0] > 1) {5      return -1;6    }7    int m = grid.length, n = grid[0].length;8    int[][] dist = new int[m][n];9    for (var e : dist) {10      Arrays.fill(e, 1 << 30);11    }12    dist[0][0] = 0;13    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[0] - b[0]);14    pq.offer(new int[]{0, 0, 0});15    int[] dirs = {-1, 0, 1, 0, -1};16    while (true) {17      var p = pq.poll();18      int i = p[1], j = p[2];19      if (i == m - 1 && j == n - 1) {20        return p[0];21      }22      for (int k = 0; k < 4; ++k) {23        int x = i + dirs[k], y = j + dirs[k + 1];24        if (x >= 0 && x < m && y >= 0 && y < n) {25          int nt = p[0] + 1;26          if (nt < grid[x][y]) {27            nt = grid[x][y] + (grid[x][y] - nt) % 2;28          }29          if (nt < dist[x][y]) {30            dist[x][y] = nt;31            pq.offer(new int[]{nt, x, y});32          }33        }34      }35    }36  }37}

1function minimumTime ( grid ) { if ( grid [ 0 ][ 1 ] > 1 && grid [ 1 ][ 0 ] > 1 ) return - 1 ; const [ m , n ] = [ grid . length , grid [ 0 ]. length ]; const DIRS = [ - 1 , 0 , 1 , 0 , - 1 ]; const q = new MinPriorityQueue ({ priority : ([ x ]) => x }); const dist = Array . from ({ length : m }, () => new Array ( n ). fill ( Number . POSITIVE_INFINITY )); dist [ 0 ][ 0 ] = 0 ; q . enqueue ([ 0 , 0 , 0 ]); while ( true ) { const [ t , i , j ] = q . dequeue (). element ; if ( i === m - 1 && j === n - 1 ) return t ; for ( let k = 0 ; k < 4 ; k ++ ) { const [ x , y ] = [ i + DIRS [ k ], j + DIRS [ k + 1 ]]; if ( x < 0 || x >= m || y < 0 || y >= n ) continue ; let nt = t + 1 ; if ( nt < grid [ x ][ y ]) { nt = grid [ x ][ y ] + (( grid [ x ][ y ] - nt ) % 2 ); } if ( nt < dist [ x ][ y ]) { dist [ x ][ y ] = nt ; q . enqueue ([ nt , x , y ]); } } } }

1class Solution {2public:3  int minimumTime(vector<vector<int>> &grid) {4    if (grid[0][1] > 1 && grid[1][0] > 1) {5      return -1;6    }7    int m = grid.size(), n = grid[0].size();8    int dist[m][n];9    memset(dist, 0x3f, sizeof dist);10    dist[0][0] = 0;11    using tii = tuple<int, int, int>;12    priority_queue<tii, vector<tii>, greater<tii>> pq;13    pq.emplace(0, 0, 0);14    int dirs[5] = {-1, 0, 1, 0, -1};15    while (1) {16      auto [t, i, j] = pq.top();17      pq.pop();18      if (i == m - 1 && j == n - 1) {19        return t;20      }21      for (int k = 0; k < 4; ++k) {22        int x = i + dirs[k], y = j + dirs[k + 1];23        if (x >= 0 && x < m && y >= 0 && y < n) {24          int nt = t + 1;25          if (nt < grid[x][y]) {26            nt = grid[x][y] + (grid[x][y] - nt) % 2;27          }28          if (nt < dist[x][y]) {29            dist[x][y] = nt;30            pq.emplace(nt, x, y);31          }32        }33      }34    }35  }36};

1class Solution:2    def minimumTime(self, grid: List[List[int]]) -> int: if grid[0][1] > 1 and grid[1][0] > 1: return - 1 m, n = len(grid), len(grid[0]) dist = [[inf] * n for _ in range(m)] dist[0][0] = 0 q = [(0, 0, 0)] dirs = (- 1, 0, 1, 0, - 1) while 1: t, i, j = heappop(q) if i == m - 1 and j == n - 1: return t for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n: nt = t + 1 if nt < grid[x][y]: nt = grid[x][y] + (grid[x][y] - nt) % 2 if nt < dist[x][y]: dist[x][y] = nt heappush(q, (nt, x, y))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem