Shortest Path in a Grid with Limited Obstacle Removal
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Shortest Path in a Grid with Limited Obstacle Removal
You are given an `m x n` integer grid `grid` where each cell is one of:
- `0` — an empty cell you can walk through, 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)`. From any cell you may move one step **up, down, left, or right** to a side-adjacent cell. You may not move diagonally and you may not leave the grid.
You are allowed to **remove at most `k` obstacles** along your route. You may step onto an obstacle cell only by spending one of your removals on it; each obstacle cell you step on consumes exactly one removal, and the total number of removals on any path can never exceed `k`. Stepping onto empty cells is always free.
Return the **minimum number of steps** needed to travel from the top-left cell to the bottom-right cell under this rule. If no such path exists, return `-1`.
The number of steps is the number of moves made; the starting cell itself counts as `0` steps.
## 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 obstacle-free path takes 10 steps. By removing the single obstacle at row 3 (0-indexed), the optimal route reaches the bottom-right corner in 6 steps.
Example 2:
```
Input:
grid = [[0,1,1],
[1,1,1],
[1,0,0]]
k = 1
Output: -1
```
Explanation: Even after removing one obstacle, there is no way to reach the bottom-right corner.
Example 3:
```
Input:
grid = [[0]]
k = 0
Output: 0
```
Explanation: The start cell is also the goal, so no moves are needed.
## Constraints
- `m == grid.length`
- `n == grid[0].length`
- `1 <= m, n <= 40`
- `1 <= m * n <= 1600`
- `grid[i][j]` is `0` or `1`
- `grid[0][0] == 0`
- `0 <= k <= m * n`
Quick Answer: This question evaluates a candidate's ability to extend classic breadth-first search into a state-augmented shortest-path problem, where the state includes both grid position and remaining obstacle-removal budget. It tests graph traversal skills, edge-case reasoning, and the ability to recognize when a standard algorithm needs an additional dimension, a pattern frequently used to assess coding and algorithms proficiency at a practical, implementation-level depth.
You are given an `m x n` integer grid `grid` where each cell is one of:
- `0` — an empty cell you can walk through, 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)`. From any cell you may move one step **up, down, left, or right** to a side-adjacent cell. You may not move diagonally and you may not leave the grid.
You are allowed to **remove at most `k` obstacles** along your route. You may step onto an obstacle cell only by spending one of your removals on it; each obstacle cell you step on consumes exactly one removal, and the total number of removals on any path can never exceed `k`. Stepping onto empty cells is always free.
Return the **minimum number of steps** needed to travel from the top-left cell to the bottom-right cell under this rule. If no such path exists, return `-1`. The number of steps is the number of moves made; the starting cell counts as `0` steps.
Write a function `shortestPath(grid, k)` that returns this minimum.
Constraints
- m == grid.length, n == grid[0].length
- 1 <= m, n <= 40
- 1 <= m * n <= 1600
- grid[i][j] is 0 or 1
- grid[0][0] == 0
- 0 <= k <= m * n
Examples
Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Expected Output: 6
Explanation: The shortest obstacle-free route takes 10 steps. Removing the single obstacle at row 3 opens a straighter path that reaches the bottom-right corner in 6 steps.
Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Expected Output: -1
Explanation: The goal is walled off by a thick band of obstacles; one removal is not enough to break through, so no valid path exists.
Input: grid = [[0]], k = 0
Expected Output: 0
Explanation: The start cell is also the goal, so zero moves are needed.
Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 2
Expected Output: 4
Explanation: Same grid as example 2, but with k = 2 you can remove the two obstacles in column 0 (cells (1,0) and (2,0)) and walk (0,0)->(1,0)->(2,0)->(2,1)->(2,2) in 4 steps.
Input: grid = [[0,1,0],[0,1,0],[0,1,0]], k = 0
Expected Output: -1
Explanation: The middle column is a solid wall of obstacles separating the two empty columns; with no removals allowed the goal is unreachable.
Input: grid = [[0,1,0],[0,1,0],[0,1,0]], k = 1
Expected Output: 4
Explanation: Removing one wall cell, e.g. (0,1), lets you cross: (0,0)->(0,1)->(0,2)->(1,2)->(2,2) in 4 steps.
Hints
- Plain BFS gives the shortest path when every move costs 1, but the twist is that a cell isn't just 'visited' or 'not' — what matters is how many obstacle removals you've spent to get there.
- Make the BFS state (row, col, obstacles_removed). Two arrivals at the same cell are different if they used a different number of removals.
- You don't need to store every removal count. For each cell, remember only the minimum removals used to reach it; re-expand a cell only if you can now reach it with strictly fewer removals.
- Cap k at m + n - 2: a shortest Manhattan path is m + n - 2 steps, so you can never benefit from more removals than that. Since all edges cost 1, the first time you enqueue the target you already have the answer.