NeetCode #636LC-2290HardAdvanced Graphs
← Back to All Problems#636 · #2290 · Minimum Obstacle Removal to Reach Corner(到达角落需要移除障碍物的最小数目)
📌 Problem Statement & Constraints
You are given an
m x n grid where 0 is empty and 1 is an obstacle. You may move in the four cardinal directions; moving into an obstacle removes it (cost 1), and moving into an empty cell is free. Return the minimum obstacles removed to reach the bottom-right from the top-left. Constraints: 1 <= m, n <= 10^5, 2 <= m * n <= 10^5.💡 Core Algorithmic Approaches
- This is a 0-1 BFS: edge weights are 0 (empty cell) or 1 (obstacle).
- Use a deque: weight-0 neighbours go to the front, weight-1 neighbours to the back.
- This keeps the deque sorted by distance, giving Dijkstra's guarantee in O(V + E).
- The answer is the distance at the bottom-right cell.
💻 Benchmark Python3 Implementation
class Solution:
def minimumObstacles(self, grid: List[List[int]]) -> int:
from collections import deque
m, n = len(grid), len(grid[0])
INF = float("inf")
dist = [[INF] * n for _ in range(m)]
dist[0][0] = 0
dq = deque([(0, 0)])
while dq:
r, c = dq.popleft()
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
w = grid[nr][nc] # 1 -> must remove an obstacle
if dist[r][c] + w < dist[nr][nc]:
dist[nr][nc] = dist[r][c] + w
if w == 0:
dq.appendleft((nr, nc)) # free move -> front
else:
dq.append((nr, nc)) # costly move -> back
return dist[m - 1][n - 1]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n): each cell is processed a constant number of times.
💾 Space Complexity
O(m * n) for the distance grid and the deque.
⚠️ Interview Pitfalls & Follow-ups
- Using a plain BFS: it ignores the obstacle cost.
- Using a heap: correct but O(log) per operation; 0-1 BFS is linear.
- Pushing to the wrong end of the deque: 0-cost neighbours go to the front.
- Marking visited instead of relaxing distances: a cheaper route to the same cell may arrive later.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.