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] == 0The key idea for solving #1293 Shortest Path in a Grid with Obstacles Elimination is to treat the grid as a graph and explore it using Breadth-First Search (BFS). Each cell represents a node, and you can move in four directions. However, the twist is that you are allowed to eliminate up to k obstacles while traveling.
To handle this constraint efficiently, extend the BFS state to include not only the position (row, col) but also the remaining number of obstacle eliminations. This means each state can be represented as (row, col, remaining_k). A visited structure should track whether a cell has been reached with a certain number of eliminations left, preventing redundant exploration.
By exploring level by level, BFS naturally guarantees the shortest path once the destination is reached. The overall complexity depends on grid size and the elimination limit, typically around O(m * n * k) time with similar space usage for visited states and the queue.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search with state (row, col, remaining_k) | O(m * n * k) | O(m * n * k) |
Algorithms Made Easy
Use these hints if you're stuck. Try solving on your own first.
Use BFS.
BFS on (x,y,r) x,y is coordinate, r is remain number of obstacles you can remove.
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.
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.
1from collections import deque
2
3def shortestPath(grid, k):
4 m, n = len(grid), len(grid[0])
5 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
6 queue = deque([(0, 0, 0, 0)])
7 visited = [[[False] * (k + 1) for _ in range(n)] for _ in range(m)]
8 visited[0][0][0] = True
9 while queue:
10 x, y, steps, remaining_k = queue.popleft()
11 if x == m - 1 and y == n - 1:
12 return steps
13 for dx, dy in directions:
14 nx, ny = x + dx, y + dy
15 if 0 <= nx < m and 0 <= ny < n:
16 new_k = remaining_k + grid[nx][ny]
17 if new_k <= k and not visited[nx][ny][new_k]:
18 visited[nx][ny][new_k] = True
19 queue.append((nx, ny, steps + 1, new_k))
20 return -1In 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.
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.
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.
1import heapq
2
3def
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Including the remaining eliminations ensures that reaching the same cell with different remaining k values is treated as different states. A path that preserves more eliminations may allow better progress later in the grid.
Yes, variations of grid BFS problems with constraints are commonly asked in FAANG and other top tech interviews. This problem tests graph traversal, state management, and optimization strategies.
A queue is used for BFS traversal, while a 3D visited structure or state tracking helps record positions along with the remaining obstacle eliminations. This prevents revisiting states that would lead to longer paths.
The optimal approach uses Breadth-First Search while tracking the remaining number of obstacle eliminations. Each state includes the grid position and remaining k value, ensuring we explore paths efficiently without revisiting weaker states.
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).