How do you solve Shortest Path in a Grid with Obstacles Elimination?

Use BFS starting from (0,0) with k eliminations available. Each step explores neighbors, decrementing eliminations when passing through obstacles. Maintain a visited set of (row, col, remaining eliminations) to prevent redundant exploration. The first time the destination is dequeued, return the number of steps taken. If the queue empties without reaching the destination, return -1.

What pattern does Shortest Path in a Grid with Obstacles Elimination use?

The Pattern: BFS (Shortest Path with State Augmentation) The Heuristic: When shortest path problems involve additional constraints or resources (like obstacle eliminations), augment the BFS state to include these parameters, and track visited states accordingly to avoid redundant or invalid paths.

Shortest Path in a Grid with Obstacles Elimination

Q: What is the time complexity of Shortest Path in a Grid with Obstacles Elimination?

O(m * n * k). Each cell can be visited with up to k+1 different remaining elimination states. BFS explores each unique state once, resulting in O(m * n * k) time.

Problem

Given a grid of 0s and 1s and an integer k, return the minimum number of steps to walk from the top-left corner to the bottom-right corner, where you can eliminate at most k obstacles (cells with 1). If it is not possible, return -1.

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 40
0 ≤ k ≤ m * n
grid[i][j] is 0 or 1

Example

Input: grid = [[0,1,1],[1,1,0],[1,0,0]], k = 1

Output: 4

Starting at (0,0), the algorithm explores neighbors using BFS while tracking remaining obstacle eliminations. It can eliminate one obstacle to move through (0,1) or (1,0). The shortest path with at most one elimination is (0,0) -> (0,1) [eliminate obstacle] -> (0,2) -> (1,2) -> (2,2), totaling 4 steps. The BFS ensures the first time the destination is reached with a valid elimination count, the path length is minimal.

Approach

Straightforward Solution

A naive BFS ignoring obstacle elimination would fail because it cannot pass through obstacles. A brute-force approach trying all paths with obstacle eliminations would be exponential and infeasible.

Core Observation

The problem requires finding the shortest path in a grid with obstacles, but with the added complexity that up to k obstacles can be eliminated. This means the state is not just the position but also how many eliminations remain, making it a multi-dimensional shortest path problem.

Path to Optimal

Preview

The key insight is to augment the BFS state with the remaining number of obstacle eliminations. This transforms the problem into a shortest path on a graph where nodes are (row, col, remaining eliminations)…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use BFS starting from (0,0) with k eliminations available. Each step explores neighbors, decrementing eliminations when passing through obstacles…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n * k)

Each cell can be visited with up to k+1 different remaining elimination states. BFS explores each unique state once, resulting in O(m * n * k) time.

Space

O(m * n * k)

The visited set and queue can hold up to O(m * n * k) states, as each position can be reached with different remaining eliminations.

Solution

Python

1from collections import deque
2
3class Solution:
  def shortestPath(self, grid: List[List[int]], k: int) -> int:
      def valid(row, col):
          return 0 <= row < m and 0 <= col < n
      
      m = len(grid)
      n = len(grid[0])
      queue = deque([(0, 0, k, 0)])
      seen = {(0, 0, k)}
      directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
      
      while queue:
          row, col, remain, steps = queue.popleft()
          if row == m - 1 and col == n - 1:
              return steps
          
          for dx, dy in directions:
              nr, nc = row + dy, col + dx
              if valid(nr, nc):
                  if grid[nr][nc] == 0:
                      if (nr, nc, remain) not in seen:
                          seen.add((nr, nc, remain))
                          queue.append((nr, nc, remain, steps + 1))
                  elif remain and (nr, nc, remain - 1) not in seen:
                      seen.add((nr, nc, remain - 1))
                      queue.append((nr, nc, remain - 1, steps + 1))
      
      return -1

Step-by-Step Solution

1

Define a Bounds-Checking Helper for Grid Coordinates

5def valid(row, col):
6    return 0 <= row < m and 0 <= col < n

Objective

To centralize the grid boundary check so neighbor exploration code stays clean, readable, and correct.

Key Insight

By isolating the bounds logic in a helper like valid(row, col), every place that needs to test a coordinate can reuse the same condition. This reduces duplication and the risk of subtle off-by-one or swapped-index bugs in the BFS loop.

Interview Quick-Check

Core Logic

The helper abstracts the row/column bounds check so the BFS body focuses on high-level state transitions instead of low-level index conditions.

State & Boundaries

The helper enforces that 0 <= row < m and 0 <= col < n, which defines the valid region of the grid.

Common Pitfalls & Bugs

Implementing the bounds check inline in multiple places or mixing up row/col ranges is a common source of index errors and incorrect traversals.

2

Initialize BFS Queue, Visited Set, and Movement Directions

To set up the initial BFS state with starting position, remaining eliminations, and data structures for traversal and visited tracking.

3

Perform BFS Traversal with State-Aware Neighbor Exploration

To explore the grid layer by layer, updating steps and remaining eliminations, and enqueueing valid next states.

4

Return -1 if Destination is Unreachable

To signal failure by returning -1 when BFS exhausts all states without reaching the target.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 16 Critical

if row == m - 1 and col == n - 1:

Check if the current position is the destination.

Because BFS explores states in order of increasing steps, the first time the destination is dequeued guarantees the shortest path, making immediate return correct and optimal.

Line 11 Critical

seen = {(0, 0, k)}

Initialize the visited set with the starting state to prevent revisiting.

Tracking visited states including remaining eliminations prevents redundant exploration and infinite loops, ensuring BFS efficiency.

Line 21 Critical

if valid(nr, nc):

Check if the neighbor is within grid boundaries.

Boundary validation prevents invalid memory access and ensures only valid cells are processed.

Full line-by-line criticality + rationale for all 22 lines available on Pro.

Test Your Understanding

Why must the BFS state include the remaining obstacle eliminations, and why is it insufficient to track only positions?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Shortest Path in a Grid with Obstacles Elimination from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Shortest Path in a Grid with Obstacles Elimination drill

or drill a free problem

1	`from collections import deque`
2
3	`class Solution:`
4	`def shortestPath(self, grid: List[List[int]], k: int) -> int:`
5	`def valid(row, col):`
6	`return 0 <= row < m and 0 <= col < n`
7
8	`m = len(grid)`
9	`n = len(grid[0])`
10	`queue = deque([(0, 0, k, 0)])`
11	`seen = {(0, 0, k)}`
12	`directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]`
13
14	`while queue:`
15	`row, col, remain, steps = queue.popleft()`
16	`if row == m - 1 and col == n - 1:`
17	`return steps`
18
19	`for dx, dy in directions:`
20	`nr, nc = row + dy, col + dx`
21	`if valid(nr, nc):`
22	`if grid[nr][nc] == 0:`
23	`if (nr, nc, remain) not in seen:`
24	`seen.add((nr, nc, remain))`
25	`queue.append((nr, nc, remain, steps + 1))`
26	`elif remain and (nr, nc, remain - 1) not in seen:`
27	`seen.add((nr, nc, remain - 1))`
28	`queue.append((nr, nc, remain - 1, steps + 1))`
29
30	`return -1`