Problem 21.7 · Breadth-First SearchHard

Minimum Obstacle Removal to Reach Corner

PatternGraph BFS Dijkstra's Shortest Path

What it teaches: 0-1 BFS: entering an empty cell costs 0, entering an obstacle costs 1.

Practise it on judges as “Minimum Obstacle Removal to Reach Corner”.

The problem

In a grid of 0 (empty) and 1 (obstacle), move up/down/left/right from the top-left to the bottom-right. Return the minimum number of obstacles you must remove. The start and end cells are empty.

Example 1

Input: grid = [[0,1,1],[1,1,0],[1,1,0]]
Output: 2

Constraints

2 ≤ rows × cols ≤ 10⁵

Pattern clues in the wording

→ Minimise a count where some steps are free
→ Edge weights are only 0 or 1

These clues point to Graph BFS: Explore from a start node in rings of increasing distance using a queue and a visited set.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int minimumObstacles(int[][] grid) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	grid = [[0,1,1],[1,1,0],[1,1,0]]	2
2	grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]	0

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. 0-1 BFS · O(rows × cols)

0-1 BFS

Time O(rows × cols) Space O(rows × cols)

dist[0][0] = 0. Pop from the front; for each neighbour with weight w = grid value, relax dist; push front if w = 0, back if w = 1.

Approach 1

import java.util.*;

class Solution {
    public 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.offerFirst(new int[]{0, 0});
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!dq.isEmpty()) {
            int[] cell = dq.pollFirst();
            int r = cell[0], c = cell[1];
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
                int w = grid[nr][nc];
                if (dist[r][c] + w >= dist[nr][nc]) continue;
                dist[nr][nc] = dist[r][c] + w;
                if (w == 0) dq.offerFirst(new int[]{nr, nc});
                else dq.offerLast(new int[]{nr, nc});
            }
        }
        return dist[m - 1][n - 1];
    }
}

Verdict: Dijkstra's result without the log factor.

Before you submit

Edge cases and common mistakes

Test these inputs

A clear path exists (0)
Single row

Mistakes people make

Plain BFS counting steps instead of obstacles.
Marking cells visited on first push (a cheaper route may come later).

Interview

Follow-up questions

What if removing an obstacle had different costs per cell?

Command Palette

The problem

Approaches

0-1 BFS

Edge cases and common mistakes

Follow-up questions