# Minimum Number of Visited Cells in a Grid
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-visited-cells-in-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-visited-cells-in-a-grid
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Stack, Heap (Priority Queue), Matrix, Monotonic Stack
**Companies:** [Huawei](https://scaleengineer.com/companies/huawei), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [WorldQuant](https://scaleengineer.com/companies/worldquant)
---
## Problem
You are given a **0-indexed** `m x n` integer matrix `grid`. Your initial position is at the **top-left** cell `(0, 0)`.

Starting from the cell `(i, j)`, you can move to one of the following cells:

* Cells `(i, k)` with `j < k <= grid[i][j] + j` (rightward movement), or
* Cells `(k, j)` with `i < k <= grid[i][j] + i` (downward movement).

Return _the minimum number of cells you need to visit to reach the **bottom-right** cell_ `(m - 1, n - 1)`. If there is no valid path, return `-1`.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-number-of-visited-cells-in-a-grid/image0.png) 

**Input:** grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]
**Output:** 4
**Explanation:** The image above shows one of the paths that visits exactly 4 cells.

**Example 2:**

![](https://assets.glich.co/dsa/minimum-number-of-visited-cells-in-a-grid/image1.png) 

**Input:** grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]
**Output:** 3
**Explanation:** The image above shows one of the paths that visits exactly 3 cells.

**Example 3:**

![](https://assets.glich.co/dsa/minimum-number-of-visited-cells-in-a-grid/image2.png) 

**Input:** grid = [[2,1,0],[1,0,0]]
**Output:** -1
**Explanation:** 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`

# Approaches
## Naive Breadth-First Search (BFS)
This problem can be modeled as finding the shortest path in an unweighted graph. The grid cells act as vertices, and the allowed moves define the edges. A standard Breadth-First Search (BFS) is a natural algorithm for finding the shortest path in terms of the number of edges (or in this case, cells visited) from a source to a destination. We start a BFS from the top-left cell `(0, 0)` and explore the grid layer by layer, where each layer corresponds to an increase in the path length.
**Time:** O(m * n * (m + n)) - In the worst case, for each of the `m * n` cells, we might iterate up to `n` cells to the right and `m` cells downwards. · **Space:** O(m * n) - for the `visited` array and the queue, which in the worst case can hold all `m * n` cells.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small grids.
**Cons:** Extremely inefficient for grids where `grid[i][j]` values are large.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.
### Explanation
The naive approach involves a straightforward implementation of BFS. We use a queue to manage the cells to visit and a 2D boolean array `visited` to avoid cycles and redundant processing. The BFS proceeds in levels, where each level corresponds to one additional step in the path. We start with the cell `(0,0)` at step 1. In each subsequent step, we explore all reachable (and unvisited) neighbors from all the cells in the current level. This continues until we either reach the destination `(m-1, n-1)` or exhaust all possible paths. The main drawback of this method is its performance. For each cell, we iterate through all possible next moves. If `grid[i][j]` is large, this leads to many iterations, making the overall complexity very high.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int minimumVisitedCells(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        if (m == 1 && n == 1) return 1;

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        
        boolean[][] visited = new boolean[m][n];
        visited[0][0] = true;

        int steps = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            steps++;
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                int r = curr[0];
                int c = curr[1];

                // Move right
                for (int k = c + 1; k < n && k <= c + grid[r][c]; k++) {
                    if (!visited[r][k]) {
                        if (r == m - 1 && k == n - 1) return steps;
                        visited[r][k] = true;
                        queue.offer(new int[]{r, k});
                    }
                }

                // Move down
                for (int k = r + 1; k < m && k <= r + grid[r][c]; k++) {
                    if (!visited[k][c]) {
                        if (k == m - 1 && c == n - 1) return steps;
                        visited[k][c] = true;
                        queue.offer(new int[]{k, c});
                    }
                }
            }
        }

        return -1;
    }
}
```
### Algorithm
1. Initialize a 2D `visited` array of size `m x n` to keep track of visited cells.
2. Create a queue for BFS and add the starting cell `(0, 0)`.
3. Mark `(0, 0)` as visited.
4. Initialize `steps = 1`.
5. Start the BFS loop which runs as long as the queue is not empty. The loop is structured to process cells level by level.
6. In each level, iterate through all cells currently in the queue.
7. For each dequeued cell `(r, c)`:
    a. Check if it's the destination `(m-1, n-1)`. If so, return the current number of steps.
    b. Explore all reachable cells to the right: for `k` from `c + 1` to `c + grid[r][c]`. If cell `(r, k)` is within bounds and not visited, mark it as visited and enqueue it.
    c. Explore all reachable cells downwards: for `k` from `r + 1` to `r + grid[r][c]`. If cell `(k, c)` is within bounds and not visited, mark it as visited and enqueue it.
8. After processing all cells in the current level, increment `steps`.
9. If the queue becomes empty and the destination has not been reached, it's impossible to get there, so return -1.

## Dynamic Programming with Priority Queues
This approach uses dynamic programming. Let `dp[i][j]` be the minimum number of cells to visit to reach cell `(i, j)`. The value of `dp[i][j]` depends on the minimum `dp` values of all previous cells that can jump to `(i, j)`. A naive DP would be slow. We can optimize the process of finding the minimum `dp` value among predecessors by using priority queues. For each row and column, a min-priority queue keeps track of the cells we've passed, ordered by their `dp` value. This allows us to quickly find the best cell to jump from.
**Time:** O(m * n * (log m + log n)) - Each cell is processed once. For each cell, we perform a few priority queue operations. The size of a row's PQ can be up to `n`, and a column's PQ up to `m`. This gives a logarithmic factor for each cell. · **Space:** O(m * n) - For the `dp` array and the priority queues, which can collectively store up to `2 * m * n` elements in the worst case.
**Pros:** Significantly more efficient than the naive approach.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** More complex to implement than the naive BFS.; The `log` factor in complexity might be a bottleneck for extremely large grids, though it passes for the given constraints.
### Explanation
We iterate through the grid from `(0,0)` to `(m-1, n-1)`, calculating `dp[i][j]` for each cell. To calculate `dp[i][j]`, we need the minimum `dp` value from a preceding cell in the same row `i` or same column `j` that can reach `(i,j)`. 

To find the minimum from the same row efficiently, we maintain a min-priority queue `rowPq` for the current row `i`. This PQ stores pairs of `(distance, index)`, ordered by distance. As we move from `j` to `j+1`, we first prune the `rowPq` by removing cells whose maximum reach falls short of `j`. The top of the `rowPq` then gives the minimum distance from a reachable predecessor in the same row. 

A similar process is applied for columns. We maintain an array of priority queues, `colPqs`, one for each column. When calculating `dp[i][j]`, we prune `colPqs[j]` and find the best predecessor from the column above. 

The final `dp[i][j]` is `1 + min(best_from_row, best_from_col)`. After computing `dp[i][j]`, we add it to both `rowPq` and `colPqs[j]` for future calculations.

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

class Solution {
    public int minimumVisitedCells(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp[0][0] = 1;

        PriorityQueue<int[]>[] colPqs = new PriorityQueue[n];
        for (int j = 0; j < n; j++) {
            colPqs[j] = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        }

        for (int i = 0; i < m; i++) {
            PriorityQueue<int[]> rowPq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
            for (int j = 0; j < n; j++) {
                while (!rowPq.isEmpty() && rowPq.peek()[1] + grid[i][rowPq.peek()[1]] < j) {
                    rowPq.poll();
                }
                while (!colPqs[j].isEmpty() && colPqs[j].peek()[1] + grid[colPqs[j].peek()[1]][j] < i) {
                    colPqs[j].poll();
                }

                int minPrevDist = Integer.MAX_VALUE;
                if (!rowPq.isEmpty()) {
                    minPrevDist = Math.min(minPrevDist, rowPq.peek()[0]);
                }
                if (!colPqs[j].isEmpty()) {
                    minPrevDist = Math.min(minPrevDist, colPqs[j].peek()[0]);
                }

                if (i > 0 || j > 0) { // Don't update dp[0][0]
                    if (minPrevDist != Integer.MAX_VALUE) {
                        dp[i][j] = minPrevDist + 1;
                    }
                }

                if (dp[i][j] != Integer.MAX_VALUE) {
                    rowPq.offer(new int[]{dp[i][j], j});
                    colPqs[j].offer(new int[]{dp[i][j], i});
                }
            }
        }

        int result = dp[m - 1][n - 1];
        return result == Integer.MAX_VALUE ? -1 : result;
    }
}
```
### Algorithm
1. Initialize a `dp[m][n]` array with infinity to store the minimum steps to reach each cell. Set `dp[0][0] = 1`.
2. Create an array of `n` min-priority queues, `colPqs`, one for each column.
3. Iterate through each row `i` from `0` to `m-1`:
    a. Create a new min-priority queue, `rowPq`, for the current row.
    b. Iterate through each column `j` from `0` to `n-1`:
        i. From `rowPq`, remove all entries `(dist, col_idx)` whose reach `col_idx + grid[i][col_idx]` is less than `j`. They cannot reach the current cell `(i, j)`.
        ii. Similarly, from `colPqs[j]`, remove entries `(dist, row_idx)` whose reach `row_idx + grid[row_idx][j]` is less than `i`.
        iii. The minimum distance to a predecessor is now at the top of `rowPq` and `colPqs[j]`. Find the minimum of these two values.
        iv. If a valid predecessor exists, update `dp[i][j] = 1 + min_predecessor_dist`.
        v. If `dp[i][j]` was updated (is not infinity), add `(dp[i][j], j)` to `rowPq` and `(dp[i][j], i)` to `colPqs[j]`.
4. The result is `dp[m-1][n-1]`. If it's still infinity, return -1.

## Dynamic Programming with Sliding Window (Deque)
This approach further optimizes the DP solution by replacing the priority queues with deques (double-ended queues) to implement a sliding window minimum algorithm. The priority queue gives us the minimum in logarithmic time, but we can achieve amortized constant time. For each row and column, we maintain a deque of indices of cells we have passed. The deque is kept monotonic with respect to the `dp` values of the cells, allowing us to find the minimum `dp` value of a reachable predecessor in O(1) time.
**Time:** O(m * n) - Each cell index is added to and removed from a row deque and a column deque at most once. All deque operations are amortized O(1). · **Space:** O(m * n) - For the `dp` array and the deques.
**Pros:** Most efficient solution with linear time complexity.; Optimal in terms of time complexity.
**Cons:** The logic for maintaining monotonic deques can be complex to implement correctly.; The constant factors might be higher than the PQ approach, though it's asymptotically faster.
### Explanation
This is the most efficient approach, building upon the DP formulation. Instead of using a priority queue which has a logarithmic time complexity for insertions and deletions, we use a deque to find the minimum in a sliding window with amortized O(1) time complexity. 

As we iterate through `(i, j)`, we maintain a `rowDeque` for row `i` and a `colDeque` for column `j`. These deques store indices, not values. They are structured to always have the index of the cell with the minimum `dp` value at the front. 

When processing `(i, j)`:
1.  We first remove indices from the front of the deques that are too far away to reach the current cell. For `rowDeque`, we remove `k` if `k + grid[i][k] < j`.
2.  The index at the front of the deque now corresponds to the best predecessor. We can retrieve its `dp` value in O(1).
3.  After calculating `dp[i][j]`, we add the current index (`j` to `rowDeque`, `i` to `colDeques[j]`) to the back of the respective deque. Before adding, we remove all indices from the back whose `dp` values are greater than or equal to `dp[i][j]`. This ensures the deque remains sorted by `dp` values, which is key to the sliding window minimum technique.

Each index is pushed and popped from each deque at most once, leading to an overall linear time complexity.

```java
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class Solution {
    public int minimumVisitedCells(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp[0][0] = 1;

        Deque<Integer>[] colDeques = new ArrayDeque[n];
        for (int j = 0; j < n; j++) {
            colDeques[j] = new ArrayDeque<>();
        }

        for (int i = 0; i < m; i++) {
            Deque<Integer> rowDeque = new ArrayDeque<>();
            for (int j = 0; j < n; j++) {
                while (!rowDeque.isEmpty() && rowDeque.peekFirst() + grid[i][rowDeque.peekFirst()] < j) {
                    rowDeque.pollFirst();
                }
                while (!colDeques[j].isEmpty() && colDeques[j].peekFirst() + grid[colDeques[j].peekFirst()][j] < i) {
                    colDeques[j].pollFirst();
                }

                int minPrevDist = Integer.MAX_VALUE;
                if (!rowDeque.isEmpty()) {
                    minPrevDist = Math.min(minPrevDist, dp[i][rowDeque.peekFirst()]);
                }
                if (!colDeques[j].isEmpty()) {
                    minPrevDist = Math.min(minPrevDist, dp[colDeques[j].peekFirst()][j]);
                }

                if (i > 0 || j > 0) { // Don't update dp[0][0]
                    if (minPrevDist != Integer.MAX_VALUE) {
                        dp[i][j] = minPrevDist + 1;
                    }
                }

                if (dp[i][j] != Integer.MAX_VALUE) {
                    while (!rowDeque.isEmpty() && dp[i][rowDeque.peekLast()] >= dp[i][j]) {
                        rowDeque.pollLast();
                    }
                    rowDeque.offerLast(j);
                    
                    while (!colDeques[j].isEmpty() && dp[colDeques[j].peekLast()][j] >= dp[i][j]) {
                        colDeques[j].pollLast();
                    }
                    colDeques[j].offerLast(i);
                }
            }
        }

        int result = dp[m - 1][n - 1];
        return result == Integer.MAX_VALUE ? -1 : result;
    }
}
```
### Algorithm
1. Initialize a `dp[m][n]` array with infinity and set `dp[0][0] = 1`.
2. Create an array of `n` deques, `colDeques`, one for each column.
3. Iterate through each row `i` from `0` to `m-1`:
    a. Create a new deque, `rowDeque`, for the current row.
    b. Iterate through each column `j` from `0` to `n-1`:
        i. Prune `rowDeque`: remove indices `k` from the front if `k + grid[i][k] < j`.
        ii. Prune `colDeques[j]`: remove indices `k` from the front if `k + grid[k][j] < i`.
        iii. The best predecessor's `dp` value is now at the front of the deques. Find the minimum.
        iv. If a valid predecessor exists, set `dp[i][j] = 1 + min_predecessor_dist`.
        v. If `dp[i][j]` is finite, add the current index to the deques while maintaining the monotonic property. For `rowDeque`, remove from the back all indices `k` where `dp[i][k] >= dp[i][j]`, then add `j`. Do similarly for `colDeques[j]` with index `i`.
4. The result is `dp[m-1][n-1]`, or -1 if it's infinity.

# Solutions
### Java

```java
class Solution {
public
  int minimumVisitedCells(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dist = new int[m][n];
    PriorityQueue<int[]>[] row = new PriorityQueue[m];
    PriorityQueue<int[]>[] col = new PriorityQueue[n];
    for (int i = 0; i < m; ++i) {
      Arrays.fill(dist[i], -1);
      row[i] =
          new PriorityQueue<>((a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    }
    for (int i = 0; i < n; ++i) {
      col[i] =
          new PriorityQueue<>((a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    }
    dist[0][0] = 1;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        while (!row[i].isEmpty() &&
               grid[i][row[i].peek()[1]] + row[i].peek()[1] < j) {
          row[i].poll();
        }
        if (!row[i].isEmpty() &&
            (dist[i][j] == -1 || row[i].peek()[0] + 1 < dist[i][j])) {
          dist[i][j] = row[i].peek()[0] + 1;
        }
        while (!col[j].isEmpty() &&
               grid[col[j].peek()[1]][j] + col[j].peek()[1] < i) {
          col[j].poll();
        }
        if (!col[j].isEmpty() &&
            (dist[i][j] == -1 || col[j].peek()[0] + 1 < dist[i][j])) {
          dist[i][j] = col[j].peek()[0] + 1;
        }
        if (dist[i][j] != -1) {
          row[i].offer(new int[]{dist[i][j], j});
          col[j].offer(new int[]{dist[i][j], i});
        }
      }
    }
    return dist[m - 1][n - 1];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumVisitedCells(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dist(m, vector<int>(n, -1));
    using pii = pair<int, int>;
    priority_queue<pii, vector<pii>, greater<pii>> row[m];
    priority_queue<pii, vector<pii>, greater<pii>> col[n];
    dist[0][0] = 1;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        while (!row[i].empty() &&
               grid[i][row[i].top().second] + row[i].top().second < j) {
          row[i].pop();
        }
        if (!row[i].empty() &&
            (dist[i][j] == -1 || row[i].top().first + 1 < dist[i][j])) {
          dist[i][j] = row[i].top().first + 1;
        }
        while (!col[j].empty() &&
               grid[col[j].top().second][j] + col[j].top().second < i) {
          col[j].pop();
        }
        if (!col[j].empty() &&
            (dist[i][j] == -1 || col[j].top().first + 1 < dist[i][j])) {
          dist[i][j] = col[j].top().first + 1;
        }
        if (dist[i][j] != -1) {
          row[i].emplace(dist[i][j], j);
          col[j].emplace(dist[i][j], i);
        }
      }
    }
    return dist[m - 1][n - 1];
  }
};

```

### Python

```python
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]

```