#2290

Hard

auto_awesomeGraph traversal with breadth-first search

LeetCode Problem Workspace

Minimum Obstacle Removal to Reach Corner

Find the minimum obstacles to remove in a 2D grid to reach the bottom-right corner using BFS graph traversal techniques.

array breadth first search graph heap priority queue matrix

Problem Statement

You are given a 0-indexed m x n grid containing 0s and 1s, where 0 represents an empty cell and 1 represents an obstacle. You can move up, down, left, or right from an empty cell to another cell.

Return the minimum number of obstacles you must remove to travel from the top-left corner (0, 0) to the bottom-right corner (m - 1, n - 1). You must plan paths to minimize removals, considering each obstacle as a weighted edge in a graph traversal.

Examples

Example 1

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

Output: 2

We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2). It can be shown that we need to remove at least 2 obstacles, so we return 2. Note that there may be other ways to remove 2 obstacles to create a path.

Example 2

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

Output: 0

We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 105
2 <= m * n <= 105
grid[i][j] is either 0 or 1.
grid[0][0] == grid[m - 1][n - 1] == 0

Solution Approach

Model the grid as a weighted graph

Treat each cell as a node and edges between adjacent cells with weight 0 for empty cells and 1 for obstacles. This sets up the grid for BFS or Dijkstra-style traversal.

Use BFS with obstacle prioritization

Implement 0-1 BFS using a deque or a priority queue to always expand the path with the fewest obstacles removed first, ensuring minimal removals are counted accurately.

Track visited states with minimal removals

Maintain a matrix of minimum obstacles removed to reach each cell to avoid revisiting with higher cost, preventing redundant exploration and guaranteeing optimal paths.

Complexity Analysis

Metric	Value
Time	O(m \cdot n)
Space	O(m \cdot n)

Time complexity is O(m \cdot n) because each cell is processed at most once in BFS. Space complexity is O(m \cdot n) to store the minimum removals matrix and the BFS queue or deque.

What Interviewers Usually Probe

Check if the candidate models grid as a graph with weighted edges.
Look for correct BFS prioritization by obstacle count.
Watch for handling visited states to avoid revisiting higher-cost paths.

Common Pitfalls or Variants

Common pitfalls

Treating all moves equally instead of assigning cost to obstacles.
Revisiting cells without checking if a path with fewer removals exists.
Failing to handle edge cases where the start or end is surrounded by obstacles.

Follow-up variants

Compute the minimum obstacles removal for multiple target cells instead of a single corner.
Allow diagonal moves and adjust BFS weights accordingly.
Return one actual path along with the minimum obstacle count.

FAQ

What is the main pattern used in Minimum Obstacle Removal to Reach Corner?

The core pattern is graph traversal with breadth-first search, treating obstacles as edges with cost to find minimal removal paths.

Can we move diagonally in this problem?

No, only up, down, left, and right moves are allowed, as diagonal moves would change the BFS edge weights and solution.

How do we track visited states effectively?

Use a matrix of the same size as the grid to record the minimal number of obstacles removed to reach each cell, ensuring no higher-cost revisits.

What data structure helps prioritize fewer obstacle paths?

A deque for 0-1 BFS or a min-heap priority queue can prioritize expansion of paths with fewer obstacles removed.

What is the expected time complexity for this problem?

The expected time complexity is O(m \cdot n) because each cell is visited at most once while exploring all paths efficiently.

terminal

Solution

Solution 1: Double-Ended Queue BFS

This problem is essentially a shortest path model, but we need to find the minimum number of obstacles to remove.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = deque([(0, 0, 0)])
        vis = set()
        dirs = (-1, 0, 1, 0, -1)
        while 1:
            i, j, k = q.popleft()
            if i == m - 1 and j == n - 1:
                return k
            if (i, j) in vis:
                continue
            vis.add((i, j))
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n:
                    if grid[x][y] == 0:
                        q.appendleft((x, y, k))
                    else:
                        q.append((x, y, k + 1))

Continue Practicing

#2577 minimum time to visit a cell in a grid #1368 minimum cost to make at least one valid path in a grid #3286 find a safe walk through a grid