Minimum Time to Visit a Cell In a Grid

Tested Python solution for LeetCode 2577 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 2577, Hard. Topics: Array, Breadth-First Search, Graph Theory, Heap (Priority Queue), Matrix, Shortest Path. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 22 parametrized pytest cases, and a playground notebook:

lcpy gen -n 2577   # by problem number
lcpy gen -s minimum_time_to_visit_a_cell_in_a_grid   # by problem name

​

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.

​

Examples

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.

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

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

import heapq


class Solution:
    # Time: O(m * n * log(m * n))
    # Space: O(m * n)
    def minimum_time(self, grid: list[list[int]]) -> int:
        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1

        rows, cols = len(grid), len(grid[0])
        unvisited = 10**18
        best = [[unvisited] * cols for _ in range(rows)]
        best[0][0] = 0
        heap: list[tuple[int, int, int]] = [(0, 0, 0)]

        while heap:
            time, row, col = heapq.heappop(heap)
            if best[row][col] < time:
                continue
            if row == rows - 1 and col == cols - 1:
                return time

            for d_row, d_col in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                n_row, n_col = row + d_row, col + d_col
                if not (0 <= n_row < rows and 0 <= n_col < cols):
                    continue
                need = grid[n_row][n_col]
                # Waiting means bouncing between two adjacent cells, which costs
                # 2 seconds per bounce, so the arrival parity is preserved.
                n_time = max(time + 1, need + ((need - time - 1) % 2))
                if n_time < best[n_row][n_col]:
                    best[n_row][n_col] = n_time
                    heapq.heappush(heap, (n_time, n_row, n_col))

        return -1

​

Complexity

Time	Space
O(m * n * log(m * n))	O(m * n)

​

Tags

NeetCode All.