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 theminimum 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.

Examples

Example 1:

$$ \begin{array}{|c|c|c|c|} \hline 0 & 1 & 3 & 2 \ \hline 5 & 1 & 2 & 5 \ \hline 4 & 3 & 8 & 6 \ \hline \end{array} $$

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

Solution

Method 1 - Using Minheap

Here is the approach:

  1. Initial Check:
    • Check and return -1 immediately if the very initial adjacent cells are not available to move.
  2. Priority Queue/Min-Heap:
    • Keep nodes (cells) in a priority queue, prioritising by the shortest estimated reach time.
  3. Visited Set:
    • Track visited nodes to ensure we do not revisit and cause cycles.
  4. Explore with BFS:
    • Use BFS to explore grid cells, adjusting based on wait times and using modulo operations to ensure transitions respect waiting times correctly.
  5. Early Exit:
    • Return the minimum time when reaching the bottom-right cell.

Code

Java
public class Solution {
    public int minimumTime(int[][] grid) {
        if (grid[0][1] > 1 && grid[1][0] > 1) return -1; // Initial edge case check

        int m = grid.length, n = grid[0].length;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.offer(new int[]{grid[0][0], 0, 0});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int time = curr[0], row = curr[1], col = curr[2];

            if (row == m - 1 && col == n - 1) return time; // Reached the bottom-right cell
            if (visited[row][col]) continue;
            visited[row][col] = true;

            for (int[] dir : dirs) {
                int r = row + dir[0], c = col + dir[1];
                if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c]) continue;
                int wait = ((grid[r][c] - time) % 2 == 0) ? 1 : 0;
                pq.offer(new int[]{Math.max(grid[r][c] + wait, time + 1), r, c});
            }
        }
        return -1;
    }
}
Python
class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        if grid[0][1] > 1 and grid[1][0] > 1:  # Initial edge case check
            return -1
        
        m, n = len(grid), len(grid[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        visited = set()
        pq = [(grid[0][0], 0, 0)]
        
        while pq:
            time, x, y = heappop(pq)
            if (x, y) in visited:
                continue
            visited.add((x, y))
            if x == m - 1 and y == n - 1:
                return time
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited:
                    wait = 1 if (grid[nx][ny] - time) % 2 == 0 else 0
                    heappush(pq, (max(grid[nx][ny] + wait, time + 1), nx, ny))
        
        return -1

Complexity

  • ⏰ Time complexity: - O(m * n log(m * n)): Due to operations on the priority queue.
  • 🧺 Space complexity: - O(m * n): For the priority queue and visited tracking.