Minimum Obstacle Removal to Reach Corner

Minimum Obstacle Removal to Reach Corner

1. What is this problem about?

You are given a 2D grid where 0 represents an empty cell and 1 represents an obstacle. You want to move from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1). You can move in four directions. The challenge is to find the minimum number of obstacles you need to remove to find a path to the destination.

2. Why is this asked in interviews?

This "Minimum Obstacle Removal to Reach Corner interview question" is a favorite at Google and TikTok because it's a perfect application of shortest-path algorithms on a graph. It tests if a candidate can model the grid as a graph where the weight of an edge is either 0 (empty cell) or 1 (obstacle cell).

3. Algorithmic pattern used

The pattern is Dijkstra's Algorithm or 0-1 BFS. Since the weights are only 0 and 1, a 0-1 BFS using a Deque (double-ended queue) is more efficient than a standard Priority Queue. You push cells with weight 0 to the front of the deque and cells with weight 1 to the back, ensuring you always process the shortest path first.

4. Example explanation

Grid: [[0, 1, 1], [1, 1, 0], [1, 1, 0]]

• Start at (0,0). Neighbors (0,1) and (1,0) are obstacles (cost 1).
• From (1,0), neighbors are (1,1) [obstacle] and (2,0) [obstacle].
• From (0,1), neighbor is (0,2) [obstacle].
• Eventually, you'll find a path like (0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2) with some removals. The BFS ensures that if there's a path with only 2 removals, we find it before exploring any paths with 3 removals.

5. Common mistakes candidates make

The most frequent mistake is using a standard BFS, which treats empty cells and obstacles the same. This only finds the path with the minimum number of steps, not the minimum number of obstacles. Another error is not using a "visited" array with distance tracking, which leads to redundant processing and potential infinite loops.

6. Interview preparation tip

Whenever you encounter a grid problem where moves have different "costs," think Dijkstra. If the costs are specifically 0 and 1, reach for the 0-1 BFS with a Deque—it's a high-signal optimization that interviewers love to see.