Minimum Obstacle Removal to Reach Corner
Understanding the Problem
We have a grid where each cell is either empty (0) or an obstacle (1). We need to travel from the top-left corner to the bottom-right corner, moving in 4 directions. We can remove obstacles along the way, but we want to remove as few as possible.
This is a shortest path problem in a different form. Moving to an empty cell costs 0 (no removal needed), and moving to an obstacle costs 1 (we remove it). We are looking for the path from (0, 0) to (m-1, n-1) with the minimum total cost, where every edge costs either 0 or 1.
Two algorithms apply. Dijkstra's algorithm handles any non-negative edge weights and gives the answer directly. When weights are limited to 0 and 1, a deque-based variant called 0-1 BFS reaches the same answer in O(V + E) time, dropping the logarithmic factor that the priority queue adds.
Key Constraints:
2 <= m * n <= 10^5: the grid holds up to 100,000 cells, so an O(m n log(m n)) solution is fast enough and an O(m n) solution is comfortable.grid[i][j]is either0or1: edge weights are limited to 0 and 1, which is the condition that makes 0-1 BFS applicable.grid[0][0] == 0andgrid[m - 1][n - 1] == 0: the start and end cells are empty, so we never pay to remove an obstacle at the corners.
Approach 1: Dijkstra's Algorithm (Min-Heap)
Intuition
Plain BFS finds the shortest path in an unweighted graph, where shortest means fewest edges. This graph is weighted: moving to an empty cell costs 0, and moving to an obstacle costs 1. Running plain BFS would minimize the number of cells visited, not the number of obstacles removed.
Dijkstra's algorithm handles this directly. Treat each cell as a node and each move to an adjacent cell as an edge whose weight equals the destination cell's value (0 or 1). Dijkstra's finds the path that minimizes total weight, which is the minimum number of obstacles removed.
The cost is the priority queue, which adds a log factor to every cell processed. With up to 10^5 cells, that is fast enough.
Algorithm
- Create a 2D distance array
distof size m x n, initialized to infinity. Setdist[0][0] = 0. - Push
(0, 0, 0)into a min-heap (priority queue), where the tuple is(cost, row, col). - While the heap is not empty, pop the element with the smallest cost.
- If we have reached
(m-1, n-1), return the cost. - If the popped cost is greater than
dist[row][col], skip it (we already found a better path). - For each of the 4 neighbors, calculate the new cost as
cost + grid[neighborRow][neighborCol]. - If the new cost is less than
dist[neighborRow][neighborCol], updatedistand push the neighbor into the heap. - Return
dist[m-1][n-1].
Example Walkthrough
Code
- Time Complexity: O(m n log(m n)). Each cell can be pushed into the priority queue at most once with a better distance. Heap operations take O(log(m n)) each.
- Space Complexity: O(m n). The distance array and priority queue each use O(m n) space.
The priority queue is the only part of Dijkstra's that exceeds linear time. Because edge weights are limited to 0 and 1, the next approach maintains the same processing order with a deque and removes the heap entirely.
Approach 2: 0-1 BFS (Optimal)
Intuition
When edge weights are limited to 0 and 1, a priority queue is not needed to process nodes in order of increasing distance. A deque (double-ended queue) maintains that order in O(1) per operation.
In plain BFS, every edge has weight 1, so the queue keeps nodes ordered by distance from the source. Here there are two kinds of edges. A 0-weight edge leads to a neighbor at the same distance as the current cell. A 1-weight edge leads to a neighbor one unit farther.
To preserve the ordering, push 0-cost neighbors to the front of the deque (same distance, process them next) and 1-cost neighbors to the back (one unit farther, process them later). The deque stays ordered by distance, the same property Dijkstra's priority queue provides, without the logarithmic cost.
0-1 BFS keeps an invariant: the distances of the cells in the deque span at most two consecutive values, d and d + 1, with all the d entries ahead of all the d + 1 entries. Popping from the front therefore always returns a cell with the smallest distance in the deque, which is the property Dijkstra's relies on.
The invariant is preserved on each pop. Say the front cell has distance d. Its 0-cost neighbors get distance d and go to the front, so they sit among the existing d entries. Its 1-cost neighbors get distance d + 1 and go to the back, behind every d entry. The deque never holds three distinct distances at once, so popping by distance order continues to hold.
Algorithm
- Create a 2D distance array
distof size m x n, initialized to infinity. Setdist[0][0] = 0. - Create a deque and push
(0, 0)to it. - While the deque is not empty, pop from the front.
- For each of the 4 neighbors, calculate the new cost as
dist[row][col] + grid[neighborRow][neighborCol]. - If the new cost is less than
dist[neighborRow][neighborCol], update it. If the edge weight is 0 (neighbor is empty), push to the front of the deque. If the edge weight is 1 (neighbor is an obstacle), push to the back. - Return
dist[m-1][n-1].
Example Walkthrough
Code
- Time Complexity: O(m * n). Each cell is pushed to and popped from the deque at most a constant number of times. All deque operations are O(1).
- Space Complexity: O(m n). The distance array and deque each use O(m n) space.