Minimum Obstacle Removal to Reach Corner

hard 0-1 bfs grid

Problem

You are given an m × n grid where each cell is either empty (0) or holds an obstacle (1). Starting from the top-left cell you can move up, down, left, or right, and you are allowed to remove any obstacle in order to walk through its cell. The two corner cells are always empty.

Return the minimum number of obstacles you must remove to travel from the top-left corner to the bottom-right corner. The grid can hold up to 10⁵ cells in total, so the solution has to be near-linear.

Inputgrid = [[0,1,1],[1,1,0],[1,1,0]]

Output2

Every route to the bottom-right corner crosses at least two obstacles — e.g. remove (0,1) and (1,1), then walk through the free cells (1,2) and (2,2).

grid (rows of 0/1, comma-separated)

from collections import deque

def minimum_obstacles(grid):
    m, n = len(grid), len(grid[0])
    dist = [[float("inf")] * n for _ in range(m)]
    dist[0][0] = 0
    dq = deque([(0, 0, 0)])  # (d, r, c)
    while dq:
        d, r, c = dq.popleft()
        if d > dist[r][c]:
            continue
        if r == m - 1 and c == n - 1:
            return d
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n:
                nd = d + grid[nr][nc]
                if nd < dist[nr][nc]:
                    dist[nr][nc] = nd
                    if grid[nr][nc] == 0:
                        dq.appendleft((nd, nr, nc))
                    else:
                        dq.append((nd, nr, nc))
    return -1

function minimumObstacles(grid) {
  const m = grid.length, n = grid[0].length;
  const dist = Array.from({ length: m }, () => new Array(n).fill(Infinity));
  dist[0][0] = 0;
  const dq = [[0, 0, 0]]; // [d, r, c]
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (dq.length) {
    const [d, r, c] = dq.shift();
    if (d > dist[r][c]) continue;
    if (r === m - 1 && c === n - 1) return d;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
      const nd = d + grid[nr][nc];
      if (nd < dist[nr][nc]) {
        dist[nr][nc] = nd;
        if (grid[nr][nc] === 0) dq.unshift([nd, nr, nc]);
        else dq.push([nd, nr, nc]);
      }
    }
  }
  return -1;
}

int minimumObstacles(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    dist[0][0] = 0;
    Deque<int[]> dq = new ArrayDeque<>();
    dq.add(new int[]{0, 0, 0}); // {d, r, c}
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!dq.isEmpty()) {
        int[] cur = dq.pollFirst();
        int d = cur[0], r = cur[1], c = cur[2];
        if (d > dist[r][c]) continue;
        if (r == m - 1 && c == n - 1) return d;
        for (int[] dir : dirs) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int nd = d + grid[nr][nc];
            if (nd < dist[nr][nc]) {
                dist[nr][nc] = nd;
                if (grid[nr][nc] == 0) dq.addFirst(new int[]{nd, nr, nc});
                else dq.addLast(new int[]{nd, nr, nc});
            }
        }
    }
    return -1;
}

int minimumObstacles(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
    dist[0][0] = 0;
    deque<array<int, 3>> dq{{0, 0, 0}}; // {d, r, c}
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!dq.empty()) {
        auto [d, r, c] = dq.front(); dq.pop_front();
        if (d > dist[r][c]) continue;
        if (r == m - 1 && c == n - 1) return d;
        for (auto& dir : dirs) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int nd = d + grid[nr][nc];
            if (nd < dist[nr][nc]) {
                dist[nr][nc] = nd;
                if (grid[nr][nc] == 0) dq.push_front({nd, nr, nc});
                else dq.push_back({nd, nr, nc});
            }
        }
    }
    return -1;
}

Explanation

Reframe the grid as a graph: stepping into a free cell costs 0 removals and stepping into an obstacle cell costs 1. The answer is then the shortest path from the top-left to the bottom-right where the path length is the total removal cost. Dijkstra with a heap solves any non-negative weights, but when every edge weighs 0 or 1 we can do better with 0-1 BFS on a plain deque.

The trick is where new cells are inserted. We always pop from the front. A neighbor reached through a free cell has the same distance as the popped cell, so it goes to the front; a neighbor reached through an obstacle costs one more, so it goes to the back. The deque therefore never holds more than two distinct distance values and stays sorted front-to-back — exactly the invariant Dijkstra's heap maintains, but every operation is O(1).

A cell can be enqueued more than once (a cheaper route may be found after an earlier push). We store the distance d inside each deque entry and skip any entry where d > dist[r][c] — it is stale. The first time the bottom-right corner is popped, its distance is final and we return it.

Walk through the default grid [[0,1,1],[1,1,0],[1,1,0]]. From (0,0) both neighbors are obstacles, so (1,0) and (0,1) get dist 1 and go to the back. Expanding them pushes (2,0), (1,1), and (0,2) at dist 2. When (1,1) is popped at cost 2, its free neighbor (1,2) keeps dist 2 and jumps to the front; (1,2) immediately chains to the free corner (2,2), also at the front. Popping (2,2) with d = 2 ends the search: remove 2 obstacles.

Each cell is relaxed from at most four neighbors and each deque operation is constant time, so the total work is O(m·n) — linear in the grid size, which is what the 10⁵-cell constraint demands. The dist table and the deque each hold at most O(m·n) entries.

Time: O(m·n) Space: O(m·n)