Watch 10 video solutions for Shortest Path in a Grid with Obstacles Elimination, a hard level problem involving Array, Breadth-First Search, Matrix. This walkthrough by Algorithms Made Easy has 17,918 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.
Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.
Example 1:
Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1 Output: 6 Explanation: The shortest path without eliminating any obstacle is 10. The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
Example 2:
Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1 Output: -1 Explanation: We need to eliminate at least two obstacles to find such a walk.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 401 <= k <= m * ngrid[i][j] is either 0 or 1.grid[0][0] == grid[m - 1][n - 1] == 0Problem Overview: You are given an m x n grid where 0 represents an empty cell and 1 represents an obstacle. Starting from the top‑left cell, reach the bottom‑right cell using the minimum number of steps. You can eliminate up to k obstacles during the path. The challenge is tracking both the grid position and how many obstacle removals remain.
Approach 1: Breadth-First Search with State Tracking (Time: O(m * n * k), Space: O(m * n * k))
This problem is a shortest path search on an unweighted grid, which naturally fits Breadth-First Search. The key twist: reaching the same cell with different remaining obstacle eliminations represents different states. Store each state as (row, col, remaining_k) in the BFS queue. When exploring neighbors, if the next cell is an obstacle, decrement the remaining eliminations. Use a 3D visited structure (or track the maximum remaining eliminations seen for each cell) to avoid revisiting weaker states. BFS guarantees the first time you reach the target is the shortest number of steps.
Approach 2: A* Search Algorithm (Time: O(m * n * k log(m * n)), Space: O(m * n * k))
A* improves the search by prioritizing states closer to the goal. Use the Manhattan distance from the current cell to the destination as the heuristic. Each node stores (steps + heuristic) as the priority while still tracking (row, col, remaining_k). This approach explores fewer states in practice because it pushes the search toward the destination instead of expanding uniformly like BFS. The grid structure from matrix problems works well with this heuristic since movement cost is uniform.
Recommended for interviews: Breadth-First Search with state tracking is the expected solution. Interviewers want to see that you model the state correctly and prevent revisiting dominated states. A* demonstrates deeper algorithm knowledge but is rarely required unless the discussion moves toward search optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search with State Tracking | O(m * n * k) | O(m * n * k) | Standard interview solution for shortest path in grids with additional state constraints |
| A* Search Algorithm | O(m * n * k log(m * n)) | O(m * n * k) | When heuristic guidance can reduce explored states and speed up practical performance |