1293. Shortest Path in a Grid with Obstacles Elimination
Asked at Databricks, DE Shaw
Difficulty
Hard
Time
O(m * n * k)
Space
O(m * n * k)
Pattern
Array
Companies
2
Problem
You are given an m x n grid. Each cell is 0 (open) or 1 (an obstacle). You start at the top-left cell (0, 0) and want to reach the bottom-right cell (m-1, n-1). In one step you move up, down, left or right to a neighboring cell.
Normally you cannot step on a 1. But you are allowed to destroy at most k obstacles along the way. Stepping onto a 1 costs one of your k destructions. Stepping onto a 0 costs nothing.
Return the minimum number of steps to reach the bottom-right cell while destroying at most k obstacles. If no such walk exists, return -1. The start and end cells are always open (0).
Walk from corner to corner, breaking at most k walls
Constraints
- ●
m == grid.length - ●
n == grid[i].length - ●
1 <= m, n <= 40 - ●
1 <= k <= m * n - ●
grid[i][j] is either 0 or 1 - ●
grid[0][0] == grid[m - 1][n - 1] == 0
Examples
grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 16grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1-1Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Databricks | Hard | View all Databricks questions → |
| DE Shaw | Hard | View all DE Shaw questions → |
How to Think About It
Brute force: Try all possible paths using DFS and track how many obstacles each path eliminates, keeping the minimum length.
Improved: Use BFS but track (row, col, obstacles_used) as state to avoid revisiting the same cell with more or equal obstacles used.
Better: BFS with a 3D visited array visited[r][c][k] where k tracks remaining eliminations.
Refined: Since BFS explores level by level, the first time you reach the target with any remaining eliminations is guaranteed to be shortest.
Optimal: BFS with state (r, c, remaining_k). Use a visited set of (r, c, remaining_k) tuples. Time O(mnk), space O(mnk).
Optimal Approach
Use BFS where each state is (row, col, remaining_k). Start from (0, 0, k) and explore all four directions. If the next cell is an obstacle, only proceed if remaining_k > 0, decrementing k. If the next cell is open, proceed without changing k. Maintain a visited set of (r, c, remaining_k) tuples to avoid cycles. BFS guarantees the first time you reach (m-1, n-1) is the shortest path. Return the distance at that point. Time complexity is O(m * n * k) since each state is visited at most once.
BFS over states (row, col, remaining_k)
Solution Code
O(m * n * k) timefrom collections import deque
def shortestPath(grid, k):
m, n = len(grid), len(grid[0])
if k >= m + n - 2:
return m + n - 2
visited = set()
visited.add((0, 0, k))
queue = deque([(0, 0, k, 0)])
while queue:
r, c, remaining, dist = queue.popleft()
if r == m - 1 and c == n - 1:
return dist
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
nk = remaining - grid[nr][nc]
if nk >= 0 and (nr, nc, nk) not in visited:
visited.add((nr, nc, nk))
queue.append((nr, nc, nk, dist + 1))
return -1Frequently Asked Questions
What is the Shortest Path in a Grid with Obstacles Elimination problem?
Given an m x n integer grid where 0 represents an open cell and 1 represents an obstacle, and an integer k, find the shortest path from the top-left to the bottom-right corner while eliminating at most k obstacles. The path cannot pass through more than k obstacles.
How do you solve Shortest Path in a Grid with Obstacles Elimination?
The optimal approach runs in O(m * n * k) time and O(m * n * k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Shortest Path in a Grid with Obstacles Elimination?
Shortest Path in a Grid with Obstacles Elimination is asked at Databricks, DE Shaw. It is a hard difficulty problem.