Minimum Number of Visited Cells in a Grid — LeetCode 2617 Python Solution
HardStackBreadth-First SearchUnion FindArrayDynamic ProgrammingMatrixMonotonic StackHeap (Priority Queue)
- Problem
- #2617
- Pattern
- Union-Find
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given a 0-indexed m x n integer matrix grid. Your initial position is at the top-left cell (0, 0).
Example
- 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.
Python solution
Python
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]Complexity
| Measure | Complexity |
|---|---|
| Time | O(m \times n \times \log (m \times n)) |
| Space | O(m \times n) auxiliary |
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2617. Minimum Number of Visited Cells in a Grid is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2617. Minimum Number of Visited Cells in a Grid?
- LeetCode 2617. Minimum Number of Visited Cells in a Grid is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2617. Minimum Number of Visited Cells in a Grid?
- The Python solution on this page runs in O(m \times n \times \log (m \times n)).
- What is the space complexity of LeetCode 2617. Minimum Number of Visited Cells in a Grid?
- The Python solution on this page uses O(m \times n) auxiliary space.
- What topics does LeetCode 2617. Minimum Number of Visited Cells in a Grid cover?
- LeetCode 2617. Minimum Number of Visited Cells in a Grid is tagged Stack, Breadth-First Search, Union Find, Array, Dynamic Programming, Matrix, Monotonic Stack and Heap (Priority Queue) on LeetCode.