# Minimum Time to Visit a Cell In a Grid
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-time-to-visit-a-cell-in-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-to-visit-a-cell-in-a-grid
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Array, Heap (Priority Queue), Matrix, Graph
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian)
---
## Problem
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 `0th` 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:**

![](https://assets.glich.co/dsa/minimum-time-to-visit-a-cell-in-a-grid/image0.png)

**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:**

![](https://assets.glich.co/dsa/minimum-time-to-visit-a-cell-in-a-grid/image1.png)

**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 <= 105`
* `0 <= grid[i][j] <= 105`
* `grid[0][0] == 0`

# Approaches
## BFS-like Approach (SPFA)
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.
**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.
**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.
### Explanation
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)`:
1.  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`.
2.  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]`).
3.  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.
4.  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.
### 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.

## Modified Dijkstra's Algorithm
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int minimumTime(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // A crucial edge case: if we cannot move from the start, it's impossible.
        if (grid[0][1] > 1 && grid[1][0] > 1) {
            return -1;
        }

        int[][] dist = new int[m][n];
        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        // PriorityQueue stores {time, row, col}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        dist[0][0] = 0;
        pq.offer(new int[]{0, 0, 0});

        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int t = curr[0];
            int r = curr[1];
            int c = curr[2];

            if (t > dist[r][c]) {
                continue;
            }

            if (r == m - 1 && c == n - 1) {
                return t;
            }

            for (int[] dir : dirs) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int newTime;
                    int requiredTime = grid[nr][nc];
                    
                    if (t + 1 >= requiredTime) {
                        newTime = t + 1;
                    } else {
                        int diff = requiredTime - t;
                        if (diff % 2 == 0) { // Same parity, need an extra step
                            newTime = requiredTime + 1;
                        } else { // Different parity, can arrive exactly at requiredTime
                            newTime = requiredTime;
                        }
                    }

                    if (newTime < dist[nr][nc]) {
                        dist[nr][nc] = newTime;
                        pq.offer(new int[]{newTime, nr, nc});
                    }
                }
            }
        }

        return -1;
    }
}
```
*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.*
### 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.

# Solutions
### Java

```java
class Solution {
public
  int minimumTime(int[][] grid) {
    if (grid[0][1] > 1 && grid[1][0] > 1) {
      return -1;
    }
    int m = grid.length, n = grid[0].length;
    int[][] dist = new int[m][n];
    for (var e : dist) {
      Arrays.fill(e, 1 << 30);
    }
    dist[0][0] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[0] - b[0]);
    pq.offer(new int[]{0, 0, 0});
    int[] dirs = {-1, 0, 1, 0, -1};
    while (true) {
      var p = pq.poll();
      int i = p[1], j = p[2];
      if (i == m - 1 && j == n - 1) {
        return p[0];
      }
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n) {
          int nt = p[0] + 1;
          if (nt < grid[x][y]) {
            nt = grid[x][y] + (grid[x][y] - nt) % 2;
          }
          if (nt < dist[x][y]) {
            dist[x][y] = nt;
            pq.offer(new int[]{nt, x, y});
          }
        }
      }
    }
  }
}

```

### JavaScript

```javascript
function 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 ]); } } } }
```

### CPP

```cpp
class Solution {
public:
  int minimumTime(vector<vector<int>> &grid) {
    if (grid[0][1] > 1 && grid[1][0] > 1) {
      return -1;
    }
    int m = grid.size(), n = grid[0].size();
    int dist[m][n];
    memset(dist, 0x3f, sizeof dist);
    dist[0][0] = 0;
    using tii = tuple<int, int, int>;
    priority_queue<tii, vector<tii>, greater<tii>> pq;
    pq.emplace(0, 0, 0);
    int dirs[5] = {-1, 0, 1, 0, -1};
    while (1) {
      auto [t, i, j] = pq.top();
      pq.pop();
      if (i == m - 1 && j == n - 1) {
        return t;
      }
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n) {
          int 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;
            pq.emplace(nt, x, y);
          }
        }
      }
    }
  }
};

```

### Python

```python
class Solution:
    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))

```