#2617

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Number of Visited Cells in a Grid

Determine the minimum number of cells to visit in a grid using state transition dynamic programming and efficient traversal techniques.

array dynamic programming stack breadth first search union find

Problem Statement

You are given an m x n integer matrix grid, where each cell contains a non-negative integer. Your start position is the top-left cell (0, 0). From a cell (i, j), you can move to any of the next grid cells in the same row or column within the range allowed by grid[i][j].

Return the minimum number of cells that must be visited to reach the bottom-right cell (m - 1, n - 1). If no valid path exists, return -1. Each move must respect the maximum jump defined by the current cell's value.

Examples

Example 1

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

Output: 4

The image above shows one of the paths that visits exactly 4 cells.

Example 2

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

Output: 3

The image above shows one of the paths that visits exactly 3 cells.

Example 3

Input: grid = [[2,1,0],[1,0,0]]

Output: -1

It can be proven that no path exists.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 105
1 <= m * n <= 105
0 <= grid[i][j] < m * n
grid[m - 1][n - 1] == 0

Solution Approach

Dynamic Programming with Distance Matrix

Maintain a DP matrix dis[i][j] representing the minimum steps to reach each cell. Initialize dis[0][0] = 1 and propagate reachable cells using the allowed jump range. Update dis[i][j] only when a smaller value is found to ensure the shortest path.

Breadth-First Search with Queue Optimization

Use BFS to explore the grid level by level, pushing cells reachable within their jump range into a queue. Track visited states using dis[i][j] to prevent revisiting cells with longer paths. This approach efficiently handles large sparse grids.

Monotonic Stack for Fast Row and Column Updates

Implement monotonic stacks for rows and columns to quickly identify the next reachable cells without scanning every cell repeatedly. This reduces redundant checks and accelerates state transitions in dynamic programming updates.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(m n) in the optimized BFS and monotonic stack solution to higher if naive scanning is used. Space complexity is O(m n) for storing the distance matrix, plus additional memory for BFS queues or stacks.

What Interviewers Usually Probe

Ask how to efficiently compute dis[i][j] for large grids without exceeding memory limits.
Probe understanding of BFS versus DP trade-offs in a matrix with jump constraints.
Check if candidates notice the importance of monotonic structures to skip redundant updates.

Common Pitfalls or Variants

Common pitfalls

Trying to scan every possible cell naively, leading to TLE in large grids.
Failing to correctly update dis[i][j] when multiple paths reach the same cell.
Ignoring the jump constraints of grid[i][j] and assuming simple adjacency moves.

Follow-up variants

Grid with weighted cells where cost is added instead of counting steps, requiring modified DP.
Allowing diagonal jumps in addition to row and column moves, increasing state space.
Dynamic grid values where jumps change after each move, necessitating adaptive DP or BFS.

FAQ

What is the best approach to find the minimum number of visited cells in a grid?

Use state transition dynamic programming combined with BFS and monotonic stacks to propagate minimum distances efficiently.

Can this problem be solved using only BFS without DP?

Yes, BFS alone works but requires careful tracking of visited cells to ensure shortest paths and avoid redundant visits.

Why is a monotonic stack useful in this problem?

It allows fast row and column updates by skipping cells that do not improve the minimum distance, reducing overall computation.

What should I do if no path exists to the bottom-right cell?

Return -1 as specified, after verifying that all reachable cells have been explored without reaching the target.

How does state transition dynamic programming apply to grid traversal problems?

It models the minimum steps to each cell as a state and updates it using previous states, ensuring the shortest path is computed efficiently.

terminal

Solution

Solution 1: Priority Queue

Let's denote the number of rows of the grid as $m$ and the number of columns as $n$. Define $dist[i][j]$ to be the shortest distance from the coordinate $(0, 0)$ to the coordinate $(i, j)$. Initially, $dist[0][0]=1$ and $dist[i][j]=-1$ for all other $i$ and $j$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def minimumVisitedCells(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dist = [[-1] * n for _ in range(m)]
        dist[0][0] = 1
        row = [[] for _ in range(m)]
        col = [[] for _ in range(n)]
        for i in range(m):
            for j in range(n):
                while row[i] and grid[i][row[i][0][1]] + row[i][0][1] < j:
                    heappop(row[i])
                if row[i] and (dist[i][j] == -1 or dist[i][j] > row[i][0][0] + 1):
                    dist[i][j] = row[i][0][0] + 1
                while col[j] and grid[col[j][0][1]][j] + col[j][0][1] < i:
                    heappop(col[j])
                if col[j] and (dist[i][j] == -1 or dist[i][j] > col[j][0][0] + 1):
                    dist[i][j] = col[j][0][0] + 1
                if dist[i][j] != -1:
                    heappush(row[i], (dist[i][j], j))
                    heappush(col[j], (dist[i][j], i))
        return dist[-1][-1]

Continue Practicing

#2503 maximum number of points from grid queries #2812 find the safest path in a grid #1631 path with minimum effort