2617. Minimum Number of Visited Cells in a Grid


Problem Description

In this problem, you are given a 2D matrix (or grid) where each cell contains a non-negative integer. Your task is to move from the top-left corner (0,0) to the bottom-right corner (m-1, n-1) of the matrix, where m is the number of rows and n is the number of columns. You can only move to the right or down, and from the current cell (i, j), you can move to any cell (i, k) where j < k <= j + grid[i][j] for rightward movement or to any cell (k, j) where i < k <= i + grid[i][j] for downward movement.

Your objective is to find the minimum number of cells you must visit to reach the bottom-right cell. If there is no way to reach the bottom-right cell, you should return -1. The essence of the problem is to find the shortest path through the grid given these movement constraints.

Intuition

To solve the problem, we can use Dijkstra's shortest path algorithm, typically used in weighted graphs to find the shortest path between two nodes. Although the given grid doesn't seem like a typical weighted graph at first glance, we can interpret each cell as a node in a graph, and the cell value represents the maximum distance (weight) you can travel in a single move from that cell. The distance from the starting cell (0, 0) to any other cell (i, j) is what we're trying to minimize.

To apply Dijkstra's algorithm, we can maintain a priority queue (min-heap) for each row and column. The reason for using priority queues is that they can efficiently provide us with the minimum distance cell that can reach our current position. A priority queue can be updated dynamically, and it can keep providing the minimum value as we progress through the matrix.

For our case, we maintain a minimum heap for every row and column. For a cell (i, j), we have two possible sources to reach it — either from a cell in the same column (above it) or from a cell in the same row (on the left). We repeatedly extract the minimum distance from the priority queues and calculate the minimum number of moves to reach our current position from those sources. While traversing, we update the distance for each cell and insert it back to the min-heaps for further traversal.

The algorithm continues this process, updating each cell's minimum distance until it reaches the bottom-right cell. Once we reach the target cell, we return the stored minimum distance, if available; otherwise, we return -1, indicating the target cell is unreachable.

Learn more about Stack, Union Find, Segment Tree, Binary Search and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

How many ways can you arrange the three letters A, B and C?

Solution Approach

The solution implements a variation of Dijkstra's algorithm to find the shortest path in a graph, tailored to the unique movement constraints of the given grid problem. Here's a step-by-step explanation of the solution approach, referencing the provided Python code and the solution's overall strategy:

  1. We initialize a 2D array dist, the same size as grid, to keep track of the minimum number of cells visited to reach each position (i, j). Initially, only the starting cell (0, 0) has a distance of 1 (since we're counting the number of cells visited), and all other distances are set to -1 to indicate they haven't been visited.

  2. We also initialize two arrays of priority queues (min-heaps), one for each row (row) and one for each column (col). The priority queues help us efficiently find the reachable cell with the shortest distance in that specific row or column.

  3. We iterate over each cell (i, j) in the grid. For each cell, we check both the corresponding row and column heaps for potential previous cells that could reach (i, j).

    • For the row heap of row i, we pop any elements for which the rightward movement to j is not possible, i.e., grid[i][row[i][0][1]] + row[i][0][1] < j. This ensures we consider only the cells within valid movement range.

    • After potentially popping these elements, if the heap is not empty, we take the top element (i.e., the cell in the same row i with the smallest distance so far) and update the distance of (i, j) if it is -1 or greater than row[i][0][0] + 1.

    • We do a similar check and update for the column heap of column j.

  4. After considering movements from the previous row and column, if the current cell's distance was updated (i.e., it is reachable), we add this distance along with the cell's coordinates to the respective row and column heaps to potentially reach further cells.

  5. This process continues for each cell in the grid. Eventually, we reach the bottom-right cell (m - 1, n - 1). The value dist[-1][-1] then represents the minimum number of cells visited to reach this target. If dist[-1][-1] remains -1, it means no valid path was found, and -1 is returned.

Lastly, the use of priority queues ensures that we always consider the shortest distance next, which is a key aspect of Dijkstra's algorithm. This algorithm is guaranteed to find the shortest path in a non-negative weighted graph, which corresponds to our grid with non-negative distances (where the weight is derived from the movement constraints rather than explicit edge weights between nodes).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Example Walkthrough

Let's illustrate the solution approach with a simple example:

Suppose we have the following grid:

1[[2, 3],
2 [1, 1]]

This grid has 2 rows and 2 columns. We want to move from the top-left corner (0,0) to the bottom-right corner (1,1) while visiting the minimum number of cells.

  1. Initialize Distance Grid: We start with initializing the dist array with the same dimensions as the grid. For this 2x2 grid, it will look like this after initialization:

    1dist = [[1, -1],
    2        [-1, -1]]

    The (0,0) cell has a distance of 1, as we're already there; all other cells are set to -1 since they haven't been visited.

  2. Initialize Priority Queues: We create two arrays of priority queues, row and col. For a 2x2 grid, there will be two rows and two columns:

    1row[0] = []  // Row 0's priority queue, starting empty
    2row[1] = []  // Row 1's priority queue, starting empty
    3col[0] = []  // Column 0's priority queue, starting empty
    4col[1] = []  // Column 1's priority queue, starting empty
  3. Iterate and Update Distances:

    • At (0,0), we can either move right or down.

    • Moving right: The value at (0,0) is 2. So we can move directly to (0,1) since 0 + 2 >= 1. Hence, update dist[0][1] to 2 because it takes one step to move from (0,0) to (0,1). After moving right:

      1dist = [[1, 2],
      2        [-1, -1]]
      3row[0] = [(2, 1)]

      We also add (2, 1) to row[0], which indicates a minimum of 2 steps are needed to reach any cell from (0,1).

    • Moving down: The value at (0,0) is still 2. So we can move directly to (1,0) since 0 + 2 >= 1. Hence, update dist[1][0] to 2 as well, for the same reason. After moving down:

      1dist = [[1, 2],
      2        [2, -1]]
      3col[0] = [(2, 1)]

      We also add (2, 1) to col[0], which indicates a minimum of 2 steps are needed to reach any cell from (1,0).

    • Now we consider cell (0,1). The priority queue for row 0 already has (2, 1), but the priority queue for column 1 is empty. Since we cannot move from (0,1) to any other cell in the same row, and there are no cells above it in the same column that meet the criteria, no further update is needed here.

    • Consider cell (1,0). Similar to (0,1), there are no cells to the left in the same row, and the priority queue for column 0 already contains (2, 1). We can't move upwards and meet the criteria.

    • Finally, we consider cell (1,1). The priority queue for row 1 is empty, but we check column 1 which contains (2, 1) from the cell (0,1). Since 1 + 1 >= 1, we can move to (1,1) from (0,1). The distance dist[0][1] is 2, so we update dist[1][1] to be 3 to reflect the new minimum distance.

  4. Final Distance Check: At the end of the iteration, our dist array is:

    1dist = [[1, 2],
    2        [2, 3]]

    The bottom-right cell (1,1) has a value of 3, meaning it takes a minimum of 3 steps to reach the target. So the output is 3.

In this example, we can see that the movement constraints allowed us to reach the bottom-right corner of the grid in 3 steps. The process of using priority queues efficiently determined the minimum number of cells visited for each possible movement within the grid, and updating the entries of our dist array ensured we always had the shortest path to work with for each subsequent move.

Solution Implementation

1from heapq import heappop, heappush
2
3class Solution:
4    def minimumVisitedCells(self, grid: List[List[int]]) -> int:
5        m, n = len(grid), len(grid[0]) # dimensions of the grid
6        distances = [[-1] * n for _ in range(m)] # to track shortest distances to each cell
7        distances[0][0] = 1 # distance to the starting cell (0, 0) is 1
8      
9        rows_heap = [[] for _ in range(m)] # heaps to store visited cells in row-wise order
10        cols_heap = [[] for _ in range(n)] # heaps to store visited cells in column-wise order
11      
12        # iterate over the grid
13        for i in range(m):
14            for j in range(n):
15                # remove cells from the row heap that are out of the reach considering current grid value
16                while rows_heap[i] and grid[i][rows_heap[i][0][1]] + rows_heap[i][0][1] < j:
17                    heappop(rows_heap[i])
18                # update the distance from the row if the new calculated distance is shorter
19                if rows_heap[i] and (distances[i][j] == -1 or distances[i][j] > rows_heap[i][0][0] + 1):
20                    distances[i][j] = rows_heap[i][0][0] + 1
21              
22                # remove cells from the column heap that are out of the reach considering current grid value
23                while cols_heap[j] and grid[cols_heap[j][0][1]][j] + cols_heap[j][0][1] < i:
24                    heappop(cols_heap[j])
25                # update the distance from the column if the new calculated distance is shorter
26                if cols_heap[j] and (distances[i][j] == -1 or distances[i][j] > cols_heap[j][0][0] + 1):
27                    distances[i][j] = cols_heap[j][0][0] + 1
28              
29                # if this cell is reachable, then add it to the heaps of both row and column
30                if distances[i][j] != -1:
31                    heappush(rows_heap[i], (distances[i][j], j))
32                    heappush(cols_heap[j], (distances[i][j], i))
33      
34        # return the distance to the bottom-right cell
35        return distances[-1][-1]
36
1import java.util.Arrays;
2import java.util.PriorityQueue;
3
4class Solution {
5    public int minimumVisitedCells(int[][] grid) {
6        // dimensions of the grid
7        int rows = grid.length, columns = grid[0].length;
8        // 2D array to store the minimum distance to reach each cell
9        int[][] distances = new int[rows][columns];
10        PriorityQueue<int[]>[] priorityQueuesForRow = new PriorityQueue[rows];
11        PriorityQueue<int[]>[] priorityQueuesForColumn = new PriorityQueue[columns];
12
13        // Initialize distances with -1 and set up the priority queues for each row and column
14        for (int i = 0; i < rows; ++i) {
15            Arrays.fill(distances[i], -1);
16            priorityQueuesForRow[i] = new PriorityQueue<>((a, b) ->
17                    a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
18        }
19        for (int j = 0; j < columns; ++j) {
20            priorityQueuesForColumn[j] = new PriorityQueue<>((a, b) ->
21                    a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
22        }
23
24        // Starting point
25        distances[0][0] = 1;
26
27        // Iterate over each cell in the grid
28        for (int i = 0; i < rows; ++i) {
29            for (int j = 0; j < columns; ++j) {
30                // Remove invalid positions from priority queue for the current row
31                while (!priorityQueuesForRow[i].isEmpty() && 
32                        grid[i][priorityQueuesForRow[i].peek()[1]] + priorityQueuesForRow[i].peek()[1] < j) {
33                    priorityQueuesForRow[i].poll();
34                }
35                // Update the distance for the current cell if needed
36                if (!priorityQueuesForRow[i].isEmpty() && 
37                        (distances[i][j] == -1 || priorityQueuesForRow[i].peek()[0] + 1 < distances[i][j])) {
38                    distances[i][j] = priorityQueuesForRow[i].peek()[0] + 1;
39                }
40
41                // Remove invalid positions from priority queue for the current column
42                while (!priorityQueuesForColumn[j].isEmpty() && 
43                        grid[priorityQueuesForColumn[j].peek()[1]][j] + priorityQueuesForColumn[j].peek()[1] < i) {
44                    priorityQueuesForColumn[j].poll();
45                }
46                // Update the distance for the current cell if needed
47                if (!priorityQueuesForColumn[j].isEmpty() && 
48                        (distances[i][j] == -1 || priorityQueuesForColumn[j].peek()[0] + 1 < distances[i][j])) {
49                    distances[i][j] = priorityQueuesForColumn[j].peek()[0] + 1;
50                }
51
52                // If the current cell is reachable, add it to the priority queues for further processing
53                if (distances[i][j] != -1) {
54                    priorityQueuesForRow[i].offer(new int[] {distances[i][j], j});
55                    priorityQueuesForColumn[j].offer(new int[] {distances[i][j], i});
56                }
57            }
58        }
59
60        // Return the minimum distance to reach the bottom-right cell of the grid
61        return distances[rows - 1][columns - 1];
62    }
63}
64
1#include <vector>
2#include <queue>
3using namespace std;
4
5class Solution {
6public:
7    int minimumVisitedCells(vector<vector<int>>& grid) {
8        // Determine the dimensions of the grid.
9        int rows = grid.size(), cols = grid[0].size();
10      
11        // Distances matrix initialized with -1 meaning unvisited.
12        vector<vector<int>> distances(rows, vector<int>(cols, -1));
13      
14        // Pair of integers definition for readability.
15        using PII = pair<int, int>;
16      
17        // Each row has its own priority queue to track minimum distance.
18        vector<priority_queue<PII, vector<PII>, greater<PII>>> rowQueues(rows);
19      
20        // Each column has its own priority queue to track minimum distance.
21        vector<priority_queue<PII, vector<PII>, greater<PII>>> columnQueues(cols);
22      
23        // Start from the top-left of the grid.
24        distances[0][0] = 1;
25
26        // Loop through each cell in the grid.
27        for (int i = 0; i < rows; ++i) {
28            for (int j = 0; j < cols; ++j) {
29                // Remove row-priority items that are out of the projectile's range.
30                while (!rowQueues[i].empty() && grid[i][rowQueues[i].top().second] + rowQueues[i].top().second < j) {
31                    rowQueues[i].pop();
32                }
33                // Update the minimal distance if necessary.
34                if (!rowQueues[i].empty() && (distances[i][j] == -1 || rowQueues[i].top().first + 1 < distances[i][j])) {
35                    distances[i][j] = rowQueues[i].top().first + 1;
36                }
37
38                // Remove column-priority items that are out of the projectile's range.
39                while (!columnQueues[j].empty() && grid[columnQueues[j].top().second][j] + columnQueues[j].top().second < i) {
40                    columnQueues[j].pop();
41                }
42                // Update the minimal distance if necessary.
43                if (!columnQueues[j].empty() && (distances[i][j] == -1 || columnQueues[j].top().first + 1 < distances[i][j])) {
44                    distances[i][j] = columnQueues[j].top().first + 1;
45                }
46
47                // If the current cell distance is not -1, add to both row and column queues.
48                if (distances[i][j] != -1) {
49                    rowQueues[i].emplace(distances[i][j], j);
50                    columnQueues[j].emplace(distances[i][j], i);
51                }
52            }
53        }
54
55        // Return the minimum distance to bottom-right corner of the grid.
56        return distances[rows - 1][cols - 1];
57    }
58};
59
60// Note: Additional includes or using namespace statement might be needed
61// depending on the context where this class is used.
62
1// Represents a two-dimensional point or a grid cell.
2type Point = [number, number];
3
4// TypeScript does not have a built-in priority queue, so we might have to implement it or use arrays in a sorted manner instead.
5// Use a simple sorted array to mimic a priority queue behavior with tuples, where the first element is distance and the second is an index.
6function insertIntoSortedQueue(queue: Point[], element: Point) {
7    const position = queue.findIndex(el => el[0] > element[0]);
8    if (position !== -1) {
9        queue.splice(position, 0, element);
10    } else {
11        queue.push(element);
12    }
13}
14
15function removeOutOfBoundElements(queue: Point[], value: number, isRow: boolean) {
16    while (queue.length > 0 && (isRow ? grid[queue[0][1]][value] + queue[0][1] : grid[value][queue[0][1]]) < value) {
17        queue.shift();  // Remove element from the start of the array.
18    }
19}
20
21// TypeScript also supports default array initialization.
22function createInitialArray(size: number): number[] {
23    return new Array(size).fill(-1);
24}
25
26// The main function to find the minimum visited cells in the grid.
27function minimumVisitedCells(grid: number[][]): number {
28    const rows = grid.length;
29    const cols = grid[0].length;
30
31    let distances = Array.from({ length: rows }, () => createInitialArray(cols));
32  
33    let rowQueues: Point[][] = Array.from({ length: rows }, () => []);
34    let colQueues: Point[][] = Array.from({ length: cols }, () => []);
35
36    distances[0][0] = 1;  // Start from the top-left of the grid.
37
38    for (let i = 0; i < rows; ++i) {
39        for (let j = 0; j < cols; ++j) {
40            removeOutOfBoundElements(rowQueues[i], j, true); // Remove out-of-range elements for the row.
41          
42            if (rowQueues[i].length > 0 && (distances[i][j] === -1 || rowQueues[i][0][0] + 1 < distances[i][j])) {
43                distances[i][j] = rowQueues[i][0][0] + 1;  // Update minimum distance.
44            }
45
46            removeOutOfBoundElements(colQueues[j], i, false); // Remove out-of-range elements for the column.
47          
48            if (colQueues[j].length > 0 && (distances[i][j] === -1 || colQueues[j][0][0] + 1 < distances[i][j])) {
49                distances[i][j] = colQueues[j][0][0] + 1;  // Update minimum distance.
50            }
51
52            // If the current cell distance is not -1, add to both row and column queues.
53            if (distances[i][j] !== -1) {
54                insertIntoSortedQueue(rowQueues[i], [distances[i][j], j]);
55                insertIntoSortedQueue(colQueues[j], [distances[i][j], i]);
56            }
57        }
58    }
59
60    // Return the minimum distance to bottom-right corner of the grid.
61    return distances[rows - 1][cols - 1];
62}
63
Not Sure What to Study? Take the 2-min Quiz:

A heap is a ...?

Time and Space Complexity

Time Complexity

The provided code has a time complexity of O(m * n * log(m * n)). This time complexity arises because in the worst case, every cell in the grid might be pushed to and popped from the heap. Each push and pop operation on a heap take O(log(k)) time where k is the number of elements in the heap. In the worst case, each row and column might contain up to m and n elements, respectively, in their heaps which contributes to the log(m) and log(n) factors. Since this push or pop operation could potentially happen for each of the m * n cells, the total time complexity accounts for m * n multiplied with the complexity of heap operations leading to O(m * n * log(m * n)).

Space Complexity

The space complexity of the code is O(m * n), which is because of the space required for the dist, row, and col arrays. The dist array has a size of m * n, where m is the number of rows and n is the number of columns in the grid. The row and col arrays store heap structures for each row and column which can also potentially store up to O(m) and O(n) elements respectively. However, due to the heaps storing pairs of data (distance and index), the constant factor is ignored in the big O notation, resulting in the space complexity remaining O(m * n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫