LeetCode 2617. Minimum Number of Visited Cells in a Grid Solution in Java, C++, Python & Go | Explanation + Code

Description

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:

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.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

Solutions

Solution 1: Priority Queue

Let's denote the number of rows of the grid as m and the number of columns as n. Define dist[i][j] to be the shortest distance from the coordinate (0, 0) to the coordinate (i, j). Initially, dist[0][0]=1 and dist[i][j]=-1 for all other i and j.

For each grid (i, j), it can come from the grid above or the grid on the left. If it comes from the grid above (i', j), where 0 ≤ i' \lt i, then (i', j) must satisfy grid[i'][j] + i' ≥ i. We need to select from these grids the one that is closest.

Therefore, we maintain a priority queue (min-heap) for each column j. Each element of the priority queue is a pair (dist[i][j], i), which represents that the shortest distance from the coordinate (0, 0) to the coordinate (i, j) is dist[i][j]. When we consider the coordinate (i, j), we only need to take out the head element (dist[i'][j], i') of the priority queue. If grid[i'][j] + i' ≥ i, we can move from the coordinate (i', j) to the coordinate (i, j). At this time, we can update the value of dist[i][j], that is, dist[i][j] = dist[i'][j] + 1, and add (dist[i][j], i) to the priority queue.

Similarly, we can maintain a priority queue for each row i and perform a similar operation.

Finally, we can obtain the shortest distance from the coordinate (0, 0) to the coordinate (m - 1, n - 1), that is, dist[m - 1][n - 1], which is the answer.

The time complexity is O(m × n × log (m × n)) and the space complexity is O(m × n). Here, m and n are the number of rows and columns of the grid, respectively.

PythonJavaC++Go

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](code-box)

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]; } }(code-box)

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]; } };(code-box)

func minimumVisitedCells(grid [][]int) int { m, n := len(grid), len(grid[0]) dist := make([][]int, m) row := make([]hp, m) col := make([]hp, n) for i := range dist { dist[i] = make([]int, n) for j := range dist[i] { dist[i][j] = -1 } } dist[0][0] = 1 for i := 0; i < m; i++ { for j := 0; j < n; j++ { for len(row[i]) > 0 && grid[i][row[i][0].second]+row[i][0].second < j { heap.Pop(&row[i]) } if len(row[i]) > 0 && (dist[i][j] == -1 || row[i][0].first+1 < dist[i][j]) { dist[i][j] = row[i][0].first + 1 } for len(col[j]) > 0 && grid[col[j][0].second][j]+col[j][0].second < i { heap.Pop(&col[j]) } if len(col[j]) > 0 && (dist[i][j] == -1 || col[j][0].first+1 < dist[i][j]) { dist[i][j] = col[j][0].first + 1 } if dist[i][j] != -1 { heap.Push(&row[i], pair{dist[i][j], j}) heap.Push(&col[j], pair{dist[i][j], i}) } } } return dist[m-1][n-1] } type pair struct { first int second int } type hp []pair func (a hp) Len() int { return len(a) } func (a hp) Swap(i, j int) { a[i], a[j] = a[j], a[i] } func (a hp) Less(i, j int) bool { return a[i].first < a[j].first || (a[i].first == a[j].first && a[i].second < a[j].second) } func (a *hp) Push(x any) { *a = append(*a, x.(pair)) } func (a *hp) Pop() any { l := len(*a); t := (*a)[l-1]; *a = (*a)[:l-1]; return t }(code-box)