Minimum Number of Visited Cells in a Grid
HardPrompt
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)withj < k <= grid[i][j] + j(rightward movement), or - Cells
(k, j)withi < 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:
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:
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:
Input: grid = [[2,1,0],[1,0,0]]
Output: -1
Explanation: It can be proven that no path exists.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1050 <= grid[i][j] < m * ngrid[m - 1][n - 1] == 0
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a 2D
visitedarray of sizem x nto keep track of visited cells. - Create a queue for BFS and add the starting cell
(0, 0). - Mark
(0, 0)as visited. - Initialize
steps = 1. - Start the BFS loop which runs as long as the queue is not empty. The loop is structured to process cells level by level.
- In each level, iterate through all cells currently in the queue.
- 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: forkfromc + 1toc + 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: forkfromr + 1tor + grid[r][c]. If cell(k, c)is within bounds and not visited, mark it as visited and enqueue it. - After processing all cells in the current level, increment
steps. - If the queue becomes empty and the destination has not been reached, it's impossible to get there, so return -1.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize a
dp[m][n]array with infinity to store the minimum steps to reach each cell. Setdp[0][0] = 1. - Create an array of
nmin-priority queues,colPqs, one for each column. - Iterate through each row
ifrom0tom-1: a. Create a new min-priority queue,rowPq, for the current row. b. Iterate through each columnjfrom0ton-1: i. FromrowPq, remove all entries(dist, col_idx)whose reachcol_idx + grid[i][col_idx]is less thanj. They cannot reach the current cell(i, j). ii. Similarly, fromcolPqs[j], remove entries(dist, row_idx)whose reachrow_idx + grid[row_idx][j]is less thani. iii. The minimum distance to a predecessor is now at the top ofrowPqandcolPqs[j]. Find the minimum of these two values. iv. If a valid predecessor exists, updatedp[i][j] = 1 + min_predecessor_dist. v. Ifdp[i][j]was updated (is not infinity), add(dp[i][j], j)torowPqand(dp[i][j], i)tocolPqs[j]. - The result is
dp[m-1][n-1]. If it's still infinity, return -1.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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
logfactor in complexity might be a bottleneck for extremely large grids, though it passes for the given constraints.
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.
Algorithm
- Initialize a
dp[m][n]array with infinity and setdp[0][0] = 1. - Create an array of
ndeques,colDeques, one for each column. - Iterate through each row
ifrom0tom-1: a. Create a new deque,rowDeque, for the current row. b. Iterate through each columnjfrom0ton-1: i. PrunerowDeque: remove indiceskfrom the front ifk + grid[i][k] < j. ii. PrunecolDeques[j]: remove indiceskfrom the front ifk + grid[k][j] < i. iii. The best predecessor'sdpvalue is now at the front of the deques. Find the minimum. iv. If a valid predecessor exists, setdp[i][j] = 1 + min_predecessor_dist. v. Ifdp[i][j]is finite, add the current index to the deques while maintaining the monotonic property. ForrowDeque, remove from the back all indiceskwheredp[i][k] >= dp[i][j], then addj. Do similarly forcolDeques[j]with indexi. - The result is
dp[m-1][n-1], or -1 if it's infinity.
Walkthrough
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):
- We first remove indices from the front of the deques that are too far away to reach the current cell. For
rowDeque, we removekifk + grid[i][k] < j. - The index at the front of the deque now corresponds to the best predecessor. We can retrieve its
dpvalue in O(1). - After calculating
dp[i][j], we add the current index (jtorowDeque,itocolDeques[j]) to the back of the respective deque. Before adding, we remove all indices from the back whosedpvalues are greater than or equal todp[i][j]. This ensures the deque remains sorted bydpvalues, 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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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]; }}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]; }};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]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.