#2577

Hard

auto_awesomeGraph traversal with breadth-first search

LeetCode Problem Workspace

Minimum Time to Visit a Cell In a Grid

Compute the fastest path in a grid where each cell has a minimum time requirement using BFS and priority queue techniques.

array breadth first search graph heap priority queue matrix

Problem Statement

You are given an m x n integer matrix grid where grid[row][col] represents the minimum time required to enter cell (row, col). You start at the top-left cell at time 0 and can move in four directions: up, down, left, and right, each taking 1 second per move.

Determine the minimum time to reach the bottom-right cell following the cell time constraints. If no path exists that satisfies all cell requirements, return -1.

Examples

Example 1

Input: grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]

Output: 7

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

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 Approach

Use BFS with a Priority Queue

Implement a priority queue to always expand the cell with the earliest reachable time. Push the starting cell with time 0, then for each move, calculate the next valid time considering the grid's constraints and push it into the queue.

Track Visited Cells Efficiently

Maintain a 2D array to record the earliest time each cell can be reached. Skip processing a cell if the current time is greater than its recorded time. This prevents revisiting cells unnecessarily and ensures the BFS explores optimally.

Handle Impossible Paths

If the priority queue is empty and the bottom-right cell has not been visited, return -1. This handles cases where grid constraints prevent any valid path from reaching the target cell.

Complexity Analysis

Metric	Value
Time	O(m \cdot n \log(m \cdot n))
Space	O(m \cdot n)

The algorithm uses O(m * n log(m * n)) time due to the priority queue operations on each of the m * n cells. Space complexity is O(m * n) for tracking visited times and queue storage.

What Interviewers Usually Probe

Focus on BFS and shortest path logic to optimize cell visit times.
Consider how cell constraints may block standard BFS paths and require a priority-based expansion.
Expect questions about handling edge cases where the target is unreachable.

Common Pitfalls or Variants

Common pitfalls

Not accounting for the minimum required time per cell can lead to invalid paths.
Using standard BFS without prioritizing earliest arrival time may miss optimal solutions.
Failing to track visited times correctly can cause unnecessary reprocessing and wrong results.

Follow-up variants

Modify the grid so certain cells have negative delays to test early arrival handling.
Use a hexagonal grid with six neighbors instead of four to adjust BFS logic.
Change the cost of moving between cells to non-uniform values to test weighted shortest paths.

FAQ

What is the main pattern used in Minimum Time to Visit a Cell In a Grid?

The problem uses graph traversal with breadth-first search combined with a priority queue to handle time constraints.

Can I use Dijkstra instead of BFS for this problem?

Yes, using Dijkstra's algorithm is equivalent since each move has a cost of 1 and the priority queue ensures the earliest arrival is expanded first.

Why might the answer be -1 in some grids?

If the constraints of grid cells prevent reaching the bottom-right cell at any valid time, the algorithm correctly returns -1.

What data structures are essential for this problem?

A priority queue for BFS expansion and a 2D array to track earliest reachable times per cell are essential.

How do I handle large grids efficiently?

Process cells using a priority queue and skip revisits using the tracked earliest time to maintain O(m * n log(m * n)) efficiency.

terminal

Solution

Solution 1: Shortest Path + Priority Queue (Min Heap)

We observe that if we cannot move at the cell $(0, 0)$, i.e., $grid[0][1] > 1$ and $grid[1][0] > 1$, then we cannot move at the cell $(0, 0)$ anymore, and we should return $-1$. For other cases, we can move.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

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))

Continue Practicing

#2290 minimum obstacle removal to reach corner #3286 find a safe walk through a grid #1368 minimum cost to make at least one valid path in a grid