⚡Flashcard Drill➔
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

  1. This is a 0-1 BFS: edge weights are 0 (empty cell) or 1 (obstacle).
  2. Use a deque: weight-0 neighbours go to the front, weight-1 neighbours to the back.
  3. This keeps the deque sorted by distance, giving Dijkstra's guarantee in O(V + E).
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems