Minimum Obstacle Removal to Reach Corner

Hard
952.

Minimum Obstacle Removal to Reach Corner

Minimum Obstacle Removal to Reach Corner is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google and Microsoft interviews.

A grid holds 0 for an empty cell and 1 for an obstacle. You may move up, down, left or right between adjacent cells, and you may remove obstacles.

Return the minimum number of obstacles to remove so that you can walk from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1). Both corners are empty.

Example 1

Input
grid = [[0,1,1],[1,1,0],[1,1,0]]
Output
2
Explanation
Remove the obstacles at `(0,1)` and `(0,2)`.

Example 2

Input
grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
Output
0
Explanation
A clear route already exists.

Example 3

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

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10^5
  • 2 <= m * n <= 10^5
  • grid[i][j] is 0 or 1
  • grid[0][0] == grid[m - 1][n - 1] == 0
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumObstacles = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Obstacle Removal to Reach Corner — Solution

Minimum Obstacle Removal to Reach Corner solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Obstacle Removal to Reach Corner is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google and Microsoft interviews.

Problem statement

A grid holds 0 for an empty cell and 1 for an obstacle. You may move up, down, left or right between adjacent cells, and you may remove obstacles.

Return the minimum number of obstacles to remove so that you can walk from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1). Both corners are empty.

Example 1

Input: grid = [[0,1,1],[1,1,0],[1,1,0]]
Output: 2
Explanation: Remove the obstacles at `(0,1)` and `(0,2)`.

Example 2

Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
Output: 0
Explanation: A clear route already exists.

Example 3

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

Constraints

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

Hints for Minimum Obstacle Removal to Reach Corner

  1. Hint 1

    Stepping onto an empty cell is free; stepping onto an obstacle costs 1.

  2. Hint 2

    So this is a shortest path where every edge weight is 0 or 1.

  3. Hint 3

    That is exactly what 0-1 BFS is for — no priority queue needed.

How to solve Minimum Obstacle Removal to Reach Corner

Give each move a cost equal to the destination cell's value and find the cheapest route. With only the weights 0 and 1, a 0-1 BFS finds it in linear time: zero-cost steps stay on the current level, one-cost steps go to the next.

Approach

  1. Set every distance to infinity except (0, 0), which is 0.
  2. Process the current level, which holds exactly the cells at distance d.
  3. Relaxing onto an empty cell keeps the distance, so append it to the current level.
  4. Relaxing onto an obstacle costs one more, so it goes to the next level.
  5. Return the distance of the bottom-right cell.

Why it works

The current level can be appended to while it is being walked, and that is precisely what makes 0-1 BFS correct: everything in it still has distance d, so the invariant "this level holds exactly the distance-d cells" survives. It gives Dijkstra's answer at BFS's cost, which matters at 10^5 cells.

Complexity

  • Time — O(m · n)
  • Space — O(m · n)

Pitfalls

  • Plain BFS counts steps, not obstacles, and answers a different question.
  • The cost belongs to the cell being entered, not the one being left.
  • A stale queue entry — one whose distance has since improved — must be skipped.

Reference solution

Python

from typing import List
from collections import deque

def minimumObstacles(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    BIG = float('inf')
    dist = [BIG] * (m * n)
    dist[0] = 0
    dq = deque([0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while dq:
        u = dq.popleft()
        r, c = divmod(u, n)
        for di, dj in dirs:
            nr, nc = r + di, c + dj
            if not (0 <= nr < m and 0 <= nc < n):
                continue
            v = nr * n + nc
            nd = dist[u] + grid[nr][nc]
            if nd >= dist[v]:
                continue
            dist[v] = nd
            if grid[nr][nc] == 0:
                dq.appendleft(v)
            else:
                dq.append(v)
    return dist[m * n - 1]

Java

public static int minimumObstacles(int[][] grid) {
    final int BIG = 1000000000;
    int m = grid.length, n = grid[0].length;
    int[] dist = new int[m * n];
    Arrays.fill(dist, BIG);
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    dist[0] = 0;
    int d = 0;
    List<Integer> cur = new ArrayList<>();
    cur.add(0);
    while (!cur.isEmpty()) {
        List<Integer> nxt = new ArrayList<>();
        for (int i = 0; i < cur.size(); i++) {
            int u = cur.get(i);
            if (dist[u] < d) continue;
            int r = u / n, c = u % n;
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                int v = nr * n + nc;
                int nd = d + grid[nr][nc];
                if (nd >= dist[v]) continue;
                dist[v] = nd;
                if (grid[nr][nc] == 0) cur.add(v);
                else nxt.add(v);
            }
        }
        cur = nxt;
        d++;
    }
    return dist[m * n - 1];
}

C++

int minimumObstacles(vector<vector<int>>& grid) {
    const int BIG = 1000000000;
    int m = (int) grid.size(), n = (int) grid[0].size();
    vector<int> dist(m * n, BIG);
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    dist[0] = 0;
    int d = 0;
    vector<int> cur = { 0 };
    while (!cur.empty()) {
        vector<int> nxt;
        for (size_t i = 0; i < cur.size(); i++) {
            int u = cur[i];
            if (dist[u] < d) continue;
            int r = u / n, c = u % n;
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                int v = nr * n + nc;
                int nd = d + grid[nr][nc];
                if (nd >= dist[v]) continue;
                dist[v] = nd;
                if (grid[nr][nc] == 0) cur.push_back(v);
                else nxt.push_back(v);
            }
        }
        cur = nxt;
        d++;
    }
    return dist[m * n - 1];
}

JavaScript

var minimumObstacles = function(grid) {
    var BIG = 1000000000;
    var m = grid.length, n = grid[0].length, i;
    var dist = [];
    for (i = 0; i < m * n; i++) dist.push(BIG);
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    dist[0] = 0;
    var d = 0;
    var cur = [0];
    while (cur.length > 0) {
        var nxt = [];
        for (i = 0; i < cur.length; i++) {
            var u = cur[i];
            if (dist[u] < d) continue;
            var r = Math.floor(u / n), c = u % n;
            for (var k = 0; k < 4; k++) {
                var nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                var v = nr * n + nc;
                var nd = d + grid[nr][nc];
                if (nd >= dist[v]) continue;
                dist[v] = nd;
                if (grid[nr][nc] === 0) cur.push(v);
                else nxt.push(v);
            }
        }
        cur = nxt;
        d++;
    }
    return dist[m * n - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal