1293. Shortest Path in a Grid with Obstacles Elimination - Detailed Explanation
Problem Statement
You’re given an m×n binary grid grid
where 0
represents an empty cell and 1
represents an obstacle. You start at the upper‑left corner (0,0)
and must reach the lower‑right corner (m−1,n−1)
. You can move up, down, left, or right one cell at a time. You are also given an integer k
—the maximum number of obstacles you can eliminate (i.e. treat as empty) along your path. Return the minimum number of steps to reach the destination, or −1
if it’s not possible within k
eliminations.
Examples
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 elimination is length 10.
By eliminating the obstacle at (1,0) or (1,1), you can cut it to 6 steps:
(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:
Even eliminating one obstacle, you cannot reach (2,2).
Constraints
m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 40
grid[i][j]
is0
or1
.0 ≤ k ≤ m·n
Hints
- A simple BFS tracks only
(i,j)
, but here you must also track how many obstacles you’ve eliminated so far. - Use a 3D visited structure or a 2D array that stores, for each cell, the fewest eliminations used to get there.
- Stop exploring a state if you’ve already arrived at the same cell with ≤ the same eliminations used.
- Since
m,n ≤ 40
, the total states(i,j,elim)
is at most 40·40·(k+1), which can be up to ~64K ifk
is large—but BFS will prune aggressively.
Approach: BFS Over (row, col, usedElim)
- State =
(r, c, e)
where(r,c)
is current position ande
is how many obstacles eliminated so far. - Queue = double‑ended queue storing states, and we track distance (steps) by level‑order traversal.
- Visited = 2D array
bestElim[r][c]
= minimume
seen so far at(r,c)
. Initialize all to +∞ exceptbestElim[0][0] = 0
. - BFS Loop:
- For each state in current level, try all four directions
(nr,nc)
. - Let
ne = e + grid[nr][nc]
(increment if obstacle). - If
ne > k
orne ≥ bestElim[nr][nc]
, skip. - Otherwise update
bestElim[nr][nc] = ne
and enqueue(nr,nc,ne)
. - If
(nr,nc)
is the target, immediately returnsteps+1
.
- For each state in current level, try all four directions
- If BFS exhausts without reaching target, return
-1
.
Step‑by‑Step Example (Example 1)
grid = [[0,0,0],
[1,1,0],
[0,0,0],
[0,1,1],
[0,0,0]], k=1
bestElim init: bestElim[0][0]=0, others=∞
queue = [(0,0,0)], steps=0
Level 0:
(0,0,0) → neighbors:
(1,0): ne = 0+1=1 ≤k and 1<∞ → bestElim[1][0]=1 enqueue (1,0,1)
(0,1): ne = 0+0=0 <∞ → bestElim[0][1]=0 enqueue (0,1,0)
Level 1 (steps=1):
process (1,0,1):
→ (2,0): ne=1+0=1 <∞ → bestElim[2][0]=1 enqueue
→ (1,1): ne=1+1=2>k skip
→ (0,0): ne=1+0=1 ≥ bestElim[0][0]=0 skip
process (0,1,0):
→ (1,1): ne=0+1=1<∞ → bestElim[1][1]=1 enqueue
→ (0,2): ne=0+0=0<∞ → bestElim[0][2]=0 enqueue
→ ...
Continue BFS; upon first reach of (4,2) we’ll be at steps=6 → return 6.
Complexity Analysis
- Time: In the worst case we explore each cell with each possible
e
from0…k
. That’sO(m·n·k)
, but pruning when a bettere
already exists often cuts this dramatically. - Space:
O(m·n)
forbestElim
plusO(m·n·k)
queue states in worst case.
Python Code
Python3
Python3
. . . .
Java Code
Java
Java
. . . .
Common Mistakes
- Using a simple
visited[r][c]
boolean and ignoring the elimination dimension leads to incorrect pruning. - Comparing
ne > bestElim[r][c]
instead ofne ≥ bestElim[r][c]
—you must allow strictly better elimination counts only. - Forgetting to check bounds or to handle
grid[0][0]
if it’s an obstacle (though typicallygrid[0][0]==0
).
Edge Cases
- Start equals end (
m=n=1
) → return 0. k
so large (≥ total obstacles) → reduces to simple Manhattan‑distance BFS =m−1 + n−1
.- Dense obstacles where narrow but long paths require exact
k
eliminations.
Related Problems
TAGS
leetcode
CONTRIBUTOR
Design Gurus Team
-
GET YOUR FREE
Coding Questions Catalog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
Related Courses
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the Coding Interview Patterns in Java, Python, JS, C++, C#, and Go. The most comprehensive course with 476 Lessons.
4.6
(69,299 learners)
New
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
3.9
(1,107 learners)
Grokking Data Structures & Algorithms for Coding Interviews
Unlock Coding Interview Success: Dive Deep into Data Structures and Algorithms.
4
(26,683 learners)
One-Stop Portal For Tech Interviews.
Copyright © 2025 Design Gurus, LLC. All rights reserved.