Shortest Path in a Grid with Obstacles Elimination

Shortest Path in a Grid with Obstacles Elimination

What is this problem about?

The Shortest Path in a Grid with Obstacles Elimination interview question gives you an m×n binary grid where 0 is walkable and 1 is an obstacle. You can eliminate at most k obstacles. Find the shortest path from the top-left corner to the bottom-right corner. If no path exists, return -1. This extends standard grid BFS with state augmentation: the BFS state includes the current position AND the number of remaining obstacle eliminations.

Why is this asked in interviews?

Apple, Uber, Meta, Amazon, Google, Bloomberg, and TikTok ask this HARD problem because it's the canonical "BFS with augmented state" problem. The insight — including the remaining k in the BFS state — converts an intractable problem into a clean O(m × n × k) BFS. It models emergency vehicle routing (ignoring some traffic lights), emergency access paths, and capacity-constrained network routing.

Algorithmic pattern used

The pattern is BFS with state (row, col, remaining_k). Initialize the BFS queue with (0, 0, k, 0 steps). For each state, try all 4 neighbors: if the neighbor is within bounds and not visited with the same or higher remaining k: if it's a 0, move there with k unchanged; if it's a 1 and k > 0, move there with k-1. Track visited states as (row, col, k) to avoid cycles. Return the number of steps when (m-1, n-1) is first reached.

Example explanation

Grid (3×3):

0 0 0
1 1 0
0 0 0

k = 1.

BFS: (0,0,k=1,steps=0) → (0,1,1,1),(1,0,0,1) [eliminate obstacle].

From (1,0,k=0): (2,0,0,2). From (0,1,k=1): (0,2,1,2),(1,1,0,2) [eliminate].

Eventually reaches (2,2) in 4 steps.

Without obstacle elimination: forced detour would take longer.

Common mistakes candidates make

• Not including k in the visited state — without it, revisiting a cell with a different remaining k would be incorrectly blocked.
• Using DFS instead of BFS — DFS finds a path but not necessarily the shortest one.
• Not handling the edge case where k >= m + n - 2 — in this case, you can eliminate all obstacles and the answer is simply m + n - 2 (Manhattan distance).
• Storing visited as (row, col) only — must be (row, col, k).

Interview preparation tip

For the Shortest Path in a Grid with Obstacles Elimination coding problem, the BFS matrix interview pattern with state augmentation is the key. The state (row, col, remaining_k) is the critical insight — without it, BFS cannot track how many eliminations are still available at each position. Snap and Oracle interviewers appreciate the early-exit optimization: if k ≥ m+n-2, return Manhattan distance immediately. Practice augmented-state BFS — it generalizes to any grid problem where movement has additional constraints like fuel, cooldown, or limited actions.