Minimum Obstacle Removal (0/1 Dijkstra)

Problem Statement

You are given an m x n grid where each cell is 0 (empty) or 1 (obstacle). Start at (0, 0) and reach (m-1, n-1) moving 4-directionally. Return the minimum number of obstacles you must remove to reach the destination.

Example 1:

Input: grid = [[0,1,1],[1,1,0],[1,1,0]]
Output: 2
Explanation: Remove 2 obstacles to form a clear path.

Example 2:

Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
Output: 0
Explanation: A path of zeros already exists.

Constraints:

• 1 <= m, n <= 10^5
• 2 <= m * n <= 10^5
• grid[i][j] is 0 or 1.

Difficulty: Hard

---

Pattern Recognition

• What is the structure of the input? A grid where edges to neighbors have weight 0 (empty) or 1 (obstacle).
• What are we optimizing? Shortest path in this binary-weighted graph.
• What pattern does this suggest? 0/1 BFS using a deque — a specialized Dijkstra for binary edge weights.
• Why does this pattern fit? With only two edge weights, you don't need a full priority queue. A deque where you push 0-edges to the front and 1-edges to the back maintains the Dijkstra invariant in O(V + E) instead of O(E log V).

---

Approach

Brute Force — Full Dijkstra with min-heap

A priority queue works correctly and gives O(E log V).

Time: O(mn log(mn)). Space: O(mn). Why insufficient: Functionally fine, but the log factor is unnecessary with 0/1 weights.

Optimal — 0/1 Deque BFS

Key Insight: Pushing 0-cost edges to the front of the deque and 1-cost edges to the back maintains the invariant that the deque front is always the node with the smallest known distance. This gives plain Dijkstra correctness without the heap's log factor.

Step-by-step:

1. Initialize dist[r][c] = infinity, dist[0][0] = 0.
2. Deque starts with [(0,0)].
3. Pop from the front. For each neighbor (nr, nc):
   • newCost = dist[r][c] + grid[nr][nc].
   • If newCost < dist[nr][nc], update it. If grid[nr][nc] == 0, push to the front; else push to the back.
4. Return dist[m-1][n-1].

Time: O(mn). Space: O(mn).

---

Walkthrough

Grid [[0,1,1],[1,1,0],[1,1,0]], target (2,2).

Initial dist:

0   inf inf
inf inf inf
inf inf inf

Deque: [(0,0)].

Pop	Neighbors	Updates	Deque
(0,0)	(0,1)=1: 1, (1,0)=1: 1	dist[0][1]=1, dist[1][0]=1	[(0,1),(1,0)] (both back)
(0,1)	(0,2)=1: 2, (1,1)=1: 2	dist[0][2]=2, dist[1][1]=2	[(1,0),(0,2),(1,1)]
(1,0)	(2,0)=1: 2, (1,1)=1: 2 -> not better	dist[2][0]=2	[(0,2),(1,1),(2,0)]
(0,2)	(1,2)=0: 2	dist[1][2]=2 (push front!)	[(1,2),(1,1),(2,0)]
(1,2)	(2,2)=0: 2	dist[2][2]=2 (push front!)	[(2,2),(1,1),(2,0)]
(2,2)	—	answer reached	—

Answer: 2.

---

Implementation

TypeScript

function minimumObstacles(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  const dist: number[][] = Array.from({ length: rows }, () => new Array(cols).fill(Infinity));
  dist[0][0] = 0;
  // Array-based deque (use real deque in production)
  const deque: Array<[number, number]> = [[0, 0]];
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

  while (deque.length > 0) {
    const [r, c] = deque.shift()!;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
      const cost = dist[r][c] + grid[nr][nc];
      if (cost < dist[nr][nc]) {
        dist[nr][nc] = cost;
        if (grid[nr][nc] === 0) deque.unshift([nr, nc]);
        else deque.push([nr, nc]);
      }
    }
  }
  return dist[rows - 1][cols - 1];
}

C++

class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));
        dist[0][0] = 0;
        deque<pair<int,int>> dq;
        dq.push_front({0, 0});
        vector<pair<int,int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!dq.empty()) {
            auto [r, c] = dq.front(); dq.pop_front();
            for (auto [dr, dc] : dirs) {
                int nr = r + dr, nc = c + dc;
                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                int cost = dist[r][c] + grid[nr][nc];
                if (cost < dist[nr][nc]) {
                    dist[nr][nc] = cost;
                    if (grid[nr][nc] == 0) dq.push_front({nr, nc});
                    else dq.push_back({nr, nc});
                }
            }
        }
        return dist[rows-1][cols-1];
    }
};

Watch out: Using Array.unshift in JS is O(n). For large grids prefer a real deque (index-tracked circular buffer) or fall back to a standard Dijkstra with a priority queue.

Watch out: The cost formula is dist[r][c] + grid[nr][nc], not dist[r][c] + 1. Entering an empty cell is free.

Watch out: Skipping the cost < dist[nr][nc] check. Without it you re-process cells and blow the complexity.

---

Complexity Analysis

	Time	Space
Full Dijkstra	O(mn log(mn))	O(mn)
0/1 Deque BFS	O(mn)	O(mn)

Bottleneck: Each cell is pushed to the deque at most twice (once via a 0-edge, once via a 1-edge), giving linear total work.

---

Edge Cases

1. Start is obstacle — Problem usually guarantees (0,0) is 0; if not, depends on contract.
2. No obstacles — Answer is 0.
3. Entirely obstacles except start and end — Answer is (m-1) + (n-1) removals needed to carve a Manhattan path.
4. 1x1 grid — Answer is 0 (or 1 if the single cell is an obstacle — edge-case dependent on spec).
5. Single row / column — Answer is the sum of obstacles in that line.

---

Related Problems

• LC 2290 — Minimum Obstacle Removal to Reach Corner: This problem.
• LC 1293 — Shortest Path in Grid with Obstacles Elimination: Augments state with "remaining eliminations" — plain BFS with (r, c, k) state.
• LC 787 — Cheapest Flights Within K Stops: Dijkstra / Bellman-Ford with hop constraint.
• LC 743 — Network Delay Time: Classic Dijkstra introduction.

---

What Is Expected at Each Level?

Junior / New Grad: Reach a Dijkstra with heap. May not know the 0/1 deque trick; nudge with "can we avoid the log?"

Mid-level: Recognize 0/1 structure and write the deque-based variant. Handle deque correctness (front for 0-cost, back for 1-cost) and the cost < dist guard.

Senior: Discuss both solutions and when each is preferable. Extend to the "limited K removals" variant (LC 1293) where state expands to (r, c, k). Talk about deque implementation realities in different languages (Array.unshift is O(n) in JS) and propose pointer-based alternatives.