Shortest Path in a Grid with Obstacles Elimination
Asked at Databricks
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | Hard | View all Databricks 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.
Solution Code
from 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Shortest Path in a Grid with Obstacles Elimination?
Shortest Path in a Grid with Obstacles Elimination is asked at Databricks. It is a hard difficulty problem.