Shortest Path in a Grid with Obstacles Elimination - Solution & Explanation
Problem Statement
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 either0or1.grid[0][0] == grid[m - 1][n - 1] == 0
Approach Overview
Problem 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 1: Breadth-First Search with State Tracking
This approach utilizes Breadth-First Search (BFS) to explore paths in the grid, while maintaining a state that includes the current position and number of obstacles removed. We can advance through the grid using BFS, and track paths using a queue where each entry consists of a tuple containing the current position, number of steps taken, and the number of obstacles removed. A three-dimensional list keeps track of states visited at any position with a particular obstacle count to avoid unnecessary reprocessing.
In the Python solution, we initiate a queue to perform BFS and a visited array to track visited states. Each state contains the (x, y) position, number of steps taken, and the number of obstacles removed. For each state, we try moving in four directions and push valid states into the queue.
Complexity
The time complexity is O(m * n * k) because we process each cell at most k times (once for each possible count of removed obstacles). The space complexity is also O(m * n * k) due to the visited array used for tracking states.
Approach 2: A* Search Algorithm
A* Search is an informed search algorithm, which is often used in pathfinding and graph traversal. For this grid problem, we use a priority queue to explore paths, using a heuristic function. The heuristic can be the Manhattan distance to the target minus the remaining k value, incentivizing routes closer to the target with lesser obstacle removals.
Leveraging a priority queue for A* search, this Python solution uses a heuristic to decide which paths to explore first. We prioritize paths by their distance to the target, pushing the states into the queue with both the actual cost (steps traveled) and the estimated cost (heuristic).
Complexity
The time complexity is generally higher than BFS due to the additional computation for the heuristic, but edges are still cut off through pruning. The space complexity remains similar to the previous method because of visited state cache retention.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search with State Tracking | The time complexity is O(m * n * k) because we process each cell at most k times (once for each possible count of removed obstacles). The space complexity is also O(m * n * k) due to the visited array used for tracking states. |
| A* Search Algorithm | The time complexity is generally higher than BFS due to the additional computation for the heuristic, but edges are still cut off through pruning. The space complexity remains similar to the previous method because of visited state cache retention. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Shortest Path in a Grid with Obstacles Elimination | Live Coding with Explanation | Leetcode - 1293 • Algorithms Made Easy • 18,236 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Shortest Path in a Grid with Obstacles Elimination easy or hard?
Shortest Path in a Grid with Obstacles Elimination Python/Java solution
How to solve Shortest Path in a Grid with Obstacles Elimination in O(m*n*k)?
What is the best approach for Shortest Path in a Grid with Obstacles Elimination?
Is Shortest Path in a Grid with Obstacles Elimination asked at Google/Amazon/Meta?
What data structure is used in Shortest Path in a Grid with Obstacles Elimination?
What is the time complexity of Shortest Path in a Grid with Obstacles Elimination?
Ready to solve this problem?
Practice Shortest Path in a Grid with Obstacles Elimination with our built-in code editor and test cases.
Practice on FleetCode