Minimum Number of Visited Cells in a Grid - Video Solutions

Problem Overview: You start at (0,0) in a grid where each cell value tells you how far you can move right or down. From cell (i,j), you can jump to any cell in the same row up to j + grid[i][j] or in the same column up to i + grid[i][j]. The task is to reach (m-1,n-1) while visiting the minimum number of cells.

Approach 1: Breadth-First Search with Row/Column Pruning (O(mn log(m+n)) time, O(mn) space)

This approach models the grid as a graph and performs Breadth-First Search from (0,0). Each step explores all reachable cells in the same row and column within the allowed jump range. A naive BFS would repeatedly scan the same row or column segments, leading to quadratic work. To avoid this, maintain ordered sets (or heaps) of unvisited indices for each row and column. When you process a cell, remove visited indices and only push valid new cells into the queue. Each cell enters the queue once, while set operations add a log factor. This guarantees that BFS levels correspond to the number of visited cells, giving the shortest path automatically.

Approach 2: Dynamic Programming with Greedy Optimization (O(mn log n) time, O(mn) space)

This method combines Dynamic Programming with greedy range queries using heaps (priority queues). Let dp[i][j] represent the minimum visited cells needed to reach (i,j). While scanning the grid row by row, maintain heaps for each row and column storing candidate cells that can reach the current position. Each heap keeps entries ordered by the best dp value. Before using a heap entry, discard it if its reachable range no longer covers the current index. The smallest valid entry gives the optimal predecessor. After computing dp[i][j], push it into the row and column heaps with its maximum reachable boundary. This avoids checking every previous cell and effectively performs greedy minimum selection within valid jump ranges.

The optimization works because each cell contributes to future transitions only within a limited interval, and heaps quickly discard outdated candidates. The idea resembles interval DP combined with monotonic pruning patterns often seen with monotonic structures.

Recommended for interviews: The BFS formulation is the most intuitive because it directly models the problem as shortest path in a grid graph. However, interviewers usually expect the optimized version that avoids scanning entire rows and columns. Showing the naive BFS first demonstrates understanding, while implementing the pruned BFS or the heap-based DP shows strong algorithmic optimization skills.