Minimum Obstacle Removal to Reach Corner — Hard Problem & Solution

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.

Difficulty: Hard
Topics: Arrays, Matrix, Breadth-First Search, Heap, Graph, Shortest Path
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

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

Set every distance to infinity except (0, 0), which is 0.
Process the current level, which holds exactly the cells at distance d.
Relaxing onto an empty cell keeps the distance, so append it to the current level.
Relaxing onto an obstacle costs one more, so it goes to the next level.
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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue