Watch 10 video solutions for Minimum Obstacle Removal to Reach Corner, a hard level problem involving Array, Breadth-First Search, Graph. This walkthrough by NeetCodeIO has 8,526 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values:
0 represents an empty cell,1 represents an obstacle that may be removed.You can move up, down, left, or right from and to an empty cell.
Return the minimum number of obstacles to remove so you can move from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1).
Example 1:
Input: grid = [[0,1,1],[1,1,0],[1,1,0]] Output: 2 Explanation: 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 Explanation: We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 1052 <= m * n <= 105grid[i][j] is either 0 or 1.grid[0][0] == grid[m - 1][n - 1] == 0Problem Overview: You start at the top-left cell of a binary grid and want to reach the bottom-right corner. Cells with 0 are free, while 1 represents an obstacle that must be removed before entering. The goal is to reach the destination while removing the minimum number of obstacles.
Approach 1: Dijkstra-like Algorithm (O(m*n log(m*n)) time, O(m*n) space)
This grid can be modeled as a weighted graph where each cell is a node. Moving into a free cell has cost 0, and moving into an obstacle has cost 1 because you must remove it. Use a priority queue to always expand the cell with the smallest accumulated obstacle removals. Maintain a distance matrix storing the minimum removals required to reach each cell. Each step explores the four directions and updates the cost using the classic relaxation step from shortest path algorithms.
The priority queue ensures the smallest removal count is processed first, exactly like Dijkstra’s algorithm on a weighted graph. This approach works reliably for any grid and is easy to reason about during interviews. Complexity is O(m*n log(m*n)) due to heap operations, and space is O(m*n) for the distance matrix and queue.
Approach 2: Dynamic Programming with Monotonic Queue (0-1 BFS) (O(m*n) time, O(m*n) space)
The key observation is that edge weights are only 0 or 1. That allows replacing the heap with a deque using the 0-1 BFS technique. When moving to a free cell (0), push the position to the front of the deque. When moving into an obstacle (1), push it to the back. This ordering guarantees cells with fewer removals are processed first without a priority queue.
You still maintain a distance matrix to avoid revisiting cells with a worse cost. Each cell is processed at most once per optimal distance update, so the total complexity becomes linear in the grid size: O(m*n). This method is a specialized optimization of Breadth-First Search for weighted edges with values 0 or 1 and is common in grid-based graph problems.
Recommended for interviews: Start by explaining the graph interpretation and the Dijkstra-style solution. Interviewers expect candidates to recognize the shortest path formulation. Then point out that weights are only 0 or 1, which enables the optimized 0-1 BFS with a deque. Demonstrating both approaches shows strong understanding of graph algorithms and practical optimization techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra-like Algorithm (Priority Queue) | O(m*n log(m*n)) | O(m*n) | General weighted grid problems where edge costs vary and a heap-based shortest path is straightforward. |
| Dynamic Programming with Monotonic Queue (0-1 BFS) | O(m*n) | O(m*n) | Best when edge weights are only 0 or 1, enabling deque-based BFS instead of a priority queue. |