# Minimum Obstacle Removal to Reach Corner
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner)
Canonical: https://scaleengineer.com/dsa/problems/minimum-obstacle-removal-to-reach-corner
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Array, Heap (Priority Queue), Matrix, Graph
---
## 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.

You can move up, down, left, or right from and to an empty cell.

Return _the **minimum** number of **obstacles** to **remove** so you can move from the upper left corner_ `(0, 0)` _to the lower right corner_ `(m - 1, n - 1)`.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-obstacle-removal-to-reach-corner/image0.png) 

**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).
It can be shown that we need to remove at least 2 obstacles, so we return 2.
Note that there may be other ways to remove 2 obstacles to create a path.

**Example 2:**

![](https://assets.glich.co/dsa/minimum-obstacle-removal-to-reach-corner/image1.png) 

**Input:** grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
**Output:** 0
**Explanation:** We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 105`
* `2 <= m * n <= 105`
* `grid[i][j]` is either `0` **or** `1`.
* `grid[0][0] == grid[m - 1][n - 1] == 0`

# Approaches
## Dijkstra's Algorithm
This problem can be modeled as finding the shortest path in a weighted graph. Each cell in the grid is a node, and there are edges between adjacent cells. The "cost" or "weight" of traversing to a cell is 0 if it's an empty cell and 1 if it's an obstacle (since we have to remove it). Dijkstra's algorithm is well-suited for finding the shortest path from a source `(0, 0)` to a destination `(m-1, n-1)` in a graph with non-negative edge weights.
**Time:** O(m * n * log(m * n)). The number of vertices `V` is `m * n`. Each push and pop operation on the priority queue takes `O(log V)` time. In the worst case, we might visit every edge once, leading to `O(E log V)` which is `O(m * n * log(m * n))` for a grid. · **Space:** O(m * n). This is for the `dist` array and the priority queue, which can store up to `m * n` elements in the worst case.
**Pros:** A standard and well-understood algorithm for shortest path problems.; Correctly handles any non-negative weighted edges.; Guaranteed to find the optimal solution.
**Cons:** The `log(V)` factor from priority queue operations makes it slightly less efficient than specialized algorithms for this specific problem where edge weights are only 0 and 1.
### Explanation
We use Dijkstra's algorithm, a classic method for finding the shortest paths in a weighted graph with non-negative weights. We maintain a distance array, `dist[m][n]`, initialized to infinity, which stores the minimum obstacles removed to reach each cell. `dist[0][0]` is set to 0. A priority queue is used to efficiently select the next cell to visit, always choosing the one that can be reached by removing the fewest obstacles so far. The priority queue stores tuples of `(obstacles, row, col)`. We start by adding `(0, 0, 0)` to the queue. In a loop, we extract the cell `(r, c)` with the minimum obstacle count `k`. If this is the destination, we've found our answer. Otherwise, for each of its four neighbors, we calculate the cost to move there (`k + grid[neighbor]`). If this new cost is better than the previously recorded distance for the neighbor, we update the distance and add the neighbor to the priority queue.

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int minimumObstacles(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        
        // PriorityQueue stores {obstacles, row, col}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        
        dist[0][0] = 0;
        pq.offer(new int[]{0, 0, 0});
        
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int obstacles = current[0];
            int r = current[1];
            int c = current[2];
            
            if (r == m - 1 && c == n - 1) {
                return obstacles;
            }
            
            if (obstacles > dist[r][c]) {
                continue;
            }
            
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int newObstacles = obstacles + grid[nr][nc];
                    if (newObstacles < dist[nr][nc]) {
                        dist[nr][nc] = newObstacles;
                        pq.offer(new int[]{newObstacles, nr, nc});
                    }
                }
            }
        }
        
        return -1; // Should not be reached
    }
}
```
### Algorithm
- Model the grid as a graph where each cell `(r, c)` is a vertex.
- The cost (or weight) of an edge from a cell to its neighbor is `0` if the neighbor is an empty cell (`grid[nr][nc] == 0`) and `1` if the neighbor is an obstacle (`grid[nr][nc] == 1`).
- The problem becomes finding the shortest path from vertex `(0, 0)` to `(m-1, n-1)`.
- Use Dijkstra's algorithm to find this shortest path.
1.  Initialize a 2D array `dist[m][n]` with a large value (infinity) to store the minimum obstacles to reach each cell. Set `dist[0][0] = 0`.
2.  Create a priority queue `pq` that sorts elements based on the number of obstacles (the first element of the tuple).
3.  Push the starting state `(0, 0, 0)` representing `(obstacles, row, col)` into `pq`.
4.  Define the four possible directions: `up, down, left, right`.
5.  Loop while `pq` is not empty:
    a. Dequeue the element with the minimum obstacles: `(k, r, c)`.
    b. If `k > dist[r][c]`, it's a stale entry, so continue.
    c. If `(r, c)` is the destination `(m-1, n-1)`, return `k`.
    d. For each valid neighbor `(nr, nc)` of `(r, c)`:
        i. Calculate the new cost to reach the neighbor: `new_cost = k + grid[nr][nc]`.
        ii. If `new_cost < dist[nr][nc]`, update `dist[nr][nc] = new_cost` and push `(new_cost, nr, nc)` into `pq`.

## 0-1 Breadth-First Search (BFS) with a Deque
Since the edge weights in our graph model are only 0 (for moving to an empty cell) or 1 (for removing an obstacle), we can use a more efficient, specialized version of Dijkstra's algorithm called 0-1 BFS. This approach uses a double-ended queue (deque) instead of a priority queue, which improves the time complexity by removing the logarithmic factor associated with priority queue operations.
**Time:** O(m * n). Each cell is enqueued and dequeued at most once. For each cell, we check its four neighbors. The total time is proportional to the number of vertices plus edges, which is `O(V + E) = O(m*n + 4*m*n) = O(m*n)`. · **Space:** O(m * n). This is for the `dist` array and the deque, which can store up to `m * n` cells in the worst case.
**Pros:** More efficient than the standard Dijkstra's algorithm for this specific problem.; Achieves optimal linear time complexity.; Conceptually simple, building upon the familiar BFS algorithm.
**Cons:** This specialized algorithm is only applicable to graphs where edge weights are restricted (typically 0 and 1).
### Explanation
The 0-1 BFS algorithm is an optimization of Dijkstra's for graphs with edge weights of only 0 or 1. It uses a deque (double-ended queue) to manage nodes to visit. The core idea is to prioritize 0-cost moves. When we explore neighbors of a cell `(r, c)`:
- If moving to a neighbor `(nr, nc)` has a cost of 0 (i.e., `grid[nr][nc] == 0`), we add the neighbor to the **front** of the deque. This ensures it will be processed before any cells that require obstacle removal.
- If moving to a neighbor has a cost of 1 (i.e., `grid[nr][nc] == 1`), we add it to the **back** of the deque.
This strategy implicitly maintains the order of cells by their path cost, ensuring that we always explore from the cell with the current minimum obstacle removal count, just like Dijkstra's, but in linear time.

```java
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class Solution {
    public int minimumObstacles(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        
        // Deque stores {row, col}
        Deque<int[]> dq = new ArrayDeque<>();
        
        dist[0][0] = 0;
        dq.offerFirst(new int[]{0, 0});
        
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        
        while (!dq.isEmpty()) {
            int[] current = dq.pollFirst();
            int r = current[0];
            int c = current[1];
            
            if (r == m - 1 && c == n - 1) {
                return dist[r][c];
            }
            
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int cost = grid[nr][nc];
                    if (dist[r][c] + cost < dist[nr][nc]) {
                        dist[nr][nc] = dist[r][c] + cost;
                        if (cost == 0) {
                            dq.offerFirst(new int[]{nr, nc});
                        } else {
                            dq.offerLast(new int[]{nr, nc});
                        }
                    }
                }
            }
        }
        
        return dist[m - 1][n - 1];
    }
}
```
### Algorithm
1.  Initialize a 2D array `dist[m][n]` with a large value (infinity) to store the minimum obstacles to reach each cell. Set `dist[0][0] = 0`.
2.  Create a deque (double-ended queue) `dq`.
3.  Add the starting cell coordinates `(0, 0)` to the *front* of the deque.
4.  Define the four possible directions: `up, down, left, right`.
5.  Loop while `dq` is not empty:
    a. Dequeue a cell `(r, c)` from the *front* of the deque.
    b. For each valid neighbor `(nr, nc)` of `(r, c)`:
        i. Let `k = dist[r][c]` be the obstacles to reach the current cell.
        ii. Calculate the cost to move to the neighbor: `cost = grid[nr][nc]`.
        iii. If `k + cost < dist[nr][nc]`:
            - Update `dist[nr][nc] = k + cost`.
            - If `cost == 0` (moving to an empty cell), add `(nr, nc)` to the *front* of the deque.
            - If `cost == 1` (removing an obstacle), add `(nr, nc)` to the *back* of the deque.
6.  After the loop, `dist[m-1][n-1]` will contain the minimum number of obstacles. Return this value.

# Solutions
### Java

```java
class Solution {
public
  int minimumObstacles(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Deque<int[]> q = new ArrayDeque<>();
    q.offer(new int[]{0, 0, 0});
    int[] dirs = {-1, 0, 1, 0, -1};
    boolean[][] vis = new boolean[m][n];
    while (true) {
      var p = q.poll();
      int i = p[0], j = p[1], k = p[2];
      if (i == m - 1 && j == n - 1) {
        return k;
      }
      if (vis[i][j]) {
        continue;
      }
      vis[i][j] = true;
      for (int h = 0; h < 4; ++h) {
        int x = i + dirs[h], y = j + dirs[h + 1];
        if (x >= 0 && x < m && y >= 0 && y < n) {
          if (grid[x][y] == 0) {
            q.offerFirst(new int[]{x, y, k});
          } else {
            q.offerLast(new int[]{x, y, k + 1});
          }
        }
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumObstacles(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    deque<tuple<int, int, int>> q{{0, 0, 0}};
    bool vis[m][n];
    memset(vis, 0, sizeof vis);
    int dirs[5] = {-1, 0, 1, 0, -1};
    while (1) {
      auto [i, j, k] = q.front();
      q.pop_front();
      if (i == m - 1 && j == n - 1) {
        return k;
      }
      if (vis[i][j]) {
        continue;
      }
      vis[i][j] = true;
      for (int h = 0; h < 4; ++h) {
        int x = i + dirs[h], y = j + dirs[h + 1];
        if (x >= 0 && x < m && y >= 0 && y < n) {
          if (grid[x][y] == 0) {
            q.push_front({x, y, k});
          } else {
            q.push_back({x, y, k + 1});
          }
        }
      }
    }
  }
};

```

### Python

```python
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))

```