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.
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:
-
We initialize a 2D array
dist
, the same size asgrid
, 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. -
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. -
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 toj
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 thanrow[i][0][0] + 1
. -
We do a similar check and update for the column heap of column
j
.
-
-
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.
-
This process continues for each cell in the grid. Eventually, we reach the bottom-right cell
(m - 1, n - 1)
. The valuedist[-1][-1]
then represents the minimum number of cells visited to reach this target. Ifdist[-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).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a simple example:
Suppose we have the following grid:
[[2, 3], [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.
-
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:dist = [[1, -1], [-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. -
Initialize Priority Queues: We create two arrays of priority queues,
row
andcol
. For a 2x2 grid, there will be two rows and two columns:row[0] = [] // Row 0's priority queue, starting empty row[1] = [] // Row 1's priority queue, starting empty col[0] = [] // Column 0's priority queue, starting empty col[1] = [] // Column 1's priority queue, starting empty
-
Iterate and Update Distances:
-
At
(0,0)
, we can either move right or down. -
Moving right: The value at
(0,0)
is2
. So we can move directly to(0,1)
since0 + 2 >= 1
. Hence, updatedist[0][1]
to2
because it takes one step to move from(0,0)
to(0,1)
. After moving right:dist = [[1, 2], [-1, -1]] row[0] = [(2, 1)]
We also add
(2, 1)
torow[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 still2
. So we can move directly to(1,0)
since0 + 2 >= 1
. Hence, updatedist[1][0]
to2
as well, for the same reason. After moving down:dist = [[1, 2], [2, -1]] col[0] = [(2, 1)]
We also add
(2, 1)
tocol[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)
. Since1 + 1 >= 1
, we can move to(1,1)
from(0,1)
. The distancedist[0][1]
is 2, so we updatedist[1][1]
to be3
to reflect the new minimum distance.
-
-
Final Distance Check: At the end of the iteration, our
dist
array is:dist = [[1, 2], [2, 3]]
The bottom-right cell
(1,1)
has a value of3
, meaning it takes a minimum of 3 steps to reach the target. So the output is3
.
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
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.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Want a Structured Path to Master System Design Too? Don’t Miss This!