#2290 Minimum Obstacle Removal to Reach Corner

frequently reported atGoogle

the problem

In plain words

grid has 0 (empty) and 1 (obstacle). Move up/down/left/right from (0, 0) to (m − 1, n − 1). Return the minimum number of obstacles you must remove.

in grid = [[0,1,1],[1,1,0],[1,1,0]]

out 2

in grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]

out 0

A clear path already exists.

1 ≤ m, n ≤ 10⁵
2 ≤ m·n ≤ 10⁵
grid[0][0] == grid[m−1][n−1] == 0

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

pattern0-1 BFS Dijkstra

Stepping onto an obstacle costs 1, onto an empty cell 0. Minimum total cost with 0/1 weights → 0-1 BFS.

solutions

From brute force to optimal

Edge weight = value of the cell you step onto. Standard heap Dijkstra.

dist[0][0] = 0.
Poll, skip stale, relax 4 neighbours with weight grid[nr][nc].
Return dist of the corner.

timeO(mn · log(mn))

4mn relaxations with heap pushes.

spaceO(mn)

dist grid and heap.

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};3 4    public int minimumObstacles(int[][] grid) {5        int rows = grid.length, cols = grid[0].length;6        int[][] dist = new int[rows][cols];7        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);8        dist[0][0] = 0;9        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));10        pq.offer(new int[] {0, 0, 0});11        while (!pq.isEmpty()) {12            int[] top = pq.poll();13            int d = top[0], r = top[1], c = top[2];14            if (d > dist[r][c]) continue;15            for (int[] dir : DIRS) {16                int nr = r + dir[0], nc = c + dir[1];17                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;18                int nd = d + grid[nr][nc];               // stepping onto an obstacle costs 119                if (nd < dist[nr][nc]) {20                    dist[nr][nc] = nd;21                    pq.offer(new int[] {nd, nr, nc});22                }23            }24        }25        return dist[rows - 1][cols - 1];26    }27}

Empty neighbours go to the deque's front, obstacles to the back. The front is always the cheapest.

dist[0][0] = 0, deque = [(0,0)].
pollFirst; for each neighbour that improves: w = 0 → offerFirst, w = 1 → offerLast.
Return dist of the corner.

timeO(mn)

Each cell is pushed at most twice; constant work per edge.

spaceO(mn)

dist grid and deque.

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};3 4    public int minimumObstacles(int[][] grid) {5        int rows = grid.length, cols = grid[0].length;6        int[][] dist = new int[rows][cols];7        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);8        dist[0][0] = 0;9        Deque<int[]> deque = new ArrayDeque<>();10        deque.offerFirst(new int[] {0, 0});11        while (!deque.isEmpty()) {12            int[] cur = deque.pollFirst();13            int r = cur[0], c = cur[1];14            for (int[] dir : DIRS) {15                int nr = r + dir[0], nc = c + dir[1];16                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;17                int w = grid[nr][nc];                     // 0 = free cell, 1 = obstacle18                if (dist[r][c] + w < dist[nr][nc]) {19                    dist[nr][nc] = dist[r][c] + w;20                    if (w == 0) deque.offerFirst(new int[] {nr, nc});21                    else deque.offerLast(new int[] {nr, nc});22                }23            }24        }25        return dist[rows - 1][cols - 1];26    }27}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};3 4    public int minimumObstacles(int[][] grid) {5        int rows = grid.length, cols = grid[0].length;6        int[][] dist = new int[rows][cols];7        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);8        dist[0][0] = 0;9        Deque<int[]> deque = new ArrayDeque<>();10        deque.offerFirst(new int[] {0, 0});11        while (!deque.isEmpty()) {12            int[] cur = deque.pollFirst();13            int r = cur[0], c = cur[1];14            for (int[] dir : DIRS) {15                int nr = r + dir[0], nc = c + dir[1];16                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;17                int w = grid[nr][nc];                     // 0 = free cell, 1 = obstacle18                if (dist[r][c] + w < dist[nr][nc]) {19                    dist[nr][nc] = dist[r][c] + w;20                    if (w == 0) deque.offerFirst(new int[] {nr, nc});21                    else deque.offerLast(new int[] {nr, nc});22                }23            }24        }25        return dist[rows - 1][cols - 1];26    }27}

in the room

How to say it in the interview

talk track

Translate: "removing an obstacle = paying 1 to enter that cell."
Name 0-1 BFS and explain why the deque stays sorted.

traps

Plain BFS counting steps — it minimises path length, not removals.
m·n up to 10⁵ with m or n up to 10⁵: allocate by rows × cols, not 10⁵ × 10⁵.

what they ask next

Follow-ups

You may remove at most k obstacles; shortest path length?

That's LC 1293: BFS over states (r, c, removalsLeft).

before you submit

Edge cases to test

A clear path exists → 0, however long it is.
A single row: the answer is the number of 1s.
m or n can be 10⁵ (but m·n ≤ 10⁵): allocate rows × cols, never 10⁵ × 10⁵.

practise next