HardNo. 2290
Minimum Obstacle Removal to Reach Corner — LeetCode 2290 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Breadth-First Search, Graph, Array, Matrix, Shortest Path, Heap (Priority Queue)
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values: 0 represents an empty cell, 1 represents an obstacle that may be removed.
Example
- Input
- grid = [[0,1,1],[1,1,0],[1,1,0]]
- Output
- 2
- Explanation
- We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2).
Python solution
class Solution:
def minimumObstacles(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
q = deque([(0, 0, 0)])
vis = set()
dirs = (-1, 0, 1, 0, -1)
while 1:
i, j, k = q.popleft()
if i == m - 1 and j == n - 1:
return k
if (i, j) in vis:
continue
vis.add((i, j))
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
if grid[x][y] == 0:
q.appendleft((x, y, k))
else:
q.append((x, y, k + 1))Complexity
- Time
- O(m × n)
- Space · auxiliary
- O(m × n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2290. Minimum Obstacle Removal to Reach Corner is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1368 | Minimum Cost to Make at Least One Valid Path in a Grid | Hard |
| 2577 | Minimum Time to Visit a Cell In a Grid | Hard |
| 0407 | Trapping Rain Water II | Hard |
| 0675 | Cut Off Trees for Golf Event | Hard |
| 0743 | Network Delay Time | Medium |
| 1263 | Minimum Moves to Move a Box to Their Target Location | Hard |
Frequently asked questions
- How hard is LeetCode 2290. Minimum Obstacle Removal to Reach Corner?
LeetCode 2290. Minimum Obstacle Removal to Reach Corner is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2290. Minimum Obstacle Removal to Reach Corner?
The Python solution on this page runs in O(m × n).
- What is the space complexity of LeetCode 2290. Minimum Obstacle Removal to Reach Corner?
The Python solution on this page uses O(m × n) auxiliary space.
- What topics does LeetCode 2290. Minimum Obstacle Removal to Reach Corner cover?
LeetCode 2290. Minimum Obstacle Removal to Reach Corner is tagged Breadth-First Search, Graph, Array, Matrix, Shortest Path and Heap (Priority Queue) on LeetCode.