Shortest Path in a Grid with Obstacles Elimination
Shortest Path in a Grid with Obstacles Elimination is a hard graphs problem solved with the bfs for shortest path pattern.
The best approach, optimal (bfs keeping the most removals per cell), runs in O(m · n · min(k, m + n)) time and O(m · n · min(k, m + n)) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from bfs over (cell, removals left) states up.
Problem
You are given an m × n grid where 0 is an empty cell and 1 is a wall, and an integer k. In one step you can move up, down, left or right to an adjacent cell inside the grid. You may walk onto a wall only by removing it, and you can remove at most k walls in total.
Starting at the top-left cell (0, 0), return the fewest steps needed to reach the bottom-right cell (m - 1, n - 1), or -1 if it cannot be reached with at most k removals.
Examples
Example 1
- Input
grid = [[0, 1, 0, 0], [0, 1, 1, 0], [0, 0, 1, 0]], k = 1- Output
5- Why
- Break the wall at (0, 1) and walk the top row: (0,0) → (0,1) → (0,2) → (0,3) → (1,3) → (2,3), 5 steps.
Example 2
- Input
grid = [[0, 1, 1], [1, 1, 1], [1, 1, 0]], k = 1- Output
-1- Why
- Every route to the corner crosses at least two walls, but only one may be removed.
Example 3
- Input
grid = [[0, 0, 0], [1, 1, 0], [0, 0, 0], [0, 1, 1], [0, 0, 0]], k = 0- Output
10- Why
- With no removals you must snake around the walls, which takes 10 steps instead of the straight-line 6.
Constraints
m == grid.length,n == grid[i].length1 <= m, n <= 400 <= k <= m * ngrid[i][j]is0(empty) or1(wall).grid[0][0] == grid[m - 1][n - 1] == 0
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| BFS over (cell, removals left) states | O(m · n · k) | O(m · n · k) |
| Optimal (BFS keeping the most removals per cell) | O(m · n · min(k, m + n)) | O(m · n · min(k, m + n)) |
1BFS over (cell, removals left) states
O(m · n · k)Each of the m·n·(k+1) states is enqueued at most once and tries 4 moves.O(m · n · k)The seen table has one flag per state.The same cell with a different number of removals left is a different situation, so make it a different node. BFS over all (row, col, left) states finds the fewest steps, because every move costs one step.
- seen[r][c][left] marks visited states. Start with (0, 0, k) at step 0.
- Process level by level. When (m - 1, n - 1) is popped, return the step count.
- For each of the 4 neighbours inside the grid: newLeft = left - grid[nr][nc].
- If newLeft >= 0 and the state is unseen, mark it and enqueue it.
- If the queue empties, return -1.
class Solution {
public int shortestPath(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
boolean[][][] seen = new boolean[m][n][k + 1];
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
Deque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[] { 0, 0, k });
seen[0][0][k] = true;
int steps = 0;
while (!queue.isEmpty()) {
for (int size = queue.size(); size > 0; size--) {
int[] cur = queue.poll();
if (cur[0] == m - 1 && cur[1] == n - 1) return steps;
for (int[] d : dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
int left = cur[2] - grid[nr][nc];
if (left >= 0 && !seen[nr][nc][left]) {
seen[nr][nc][left] = true;
queue.offer(new int[] { nr, nc, left });
}
}
}
steps++;
}
return -1;
}
}class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
seen = [[[False] * (k + 1) for _ in range(n)] for _ in range(m)]
seen[0][0][k] = True
queue = deque([(0, 0, k)])
steps = 0
while queue:
for _ in range(len(queue)):
r, c, left = queue.popleft()
if r == m - 1 and c == n - 1:
return steps
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
nl = left - grid[nr][nc]
if nl >= 0 and not seen[nr][nc][nl]:
seen[nr][nc][nl] = True
queue.append((nr, nc, nl))
steps += 1
return -1class Solution {
public:
int shortestPath(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
vector<vector<vector<bool>>> seen(m, vector<vector<bool>>(n, vector<bool>(k + 1, false)));
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
queue<array<int, 3>> q;
q.push({0, 0, k});
seen[0][0][k] = true;
int steps = 0;
while (!q.empty()) {
for (int size = q.size(); size > 0; size--) {
auto [r, c, left] = q.front();
q.pop();
if (r == m - 1 && c == n - 1) return steps;
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
int nl = left - grid[nr][nc];
if (nl >= 0 && !seen[nr][nc][nl]) {
seen[nr][nc][nl] = true;
q.push({nr, nc, nl});
}
}
}
steps++;
}
return -1;
}
};function shortestPath(grid, k) {
const m = grid.length, n = grid[0].length;
const seen = new Uint8Array(m * n * (k + 1));
const id = (r, c, l) => (r * n + c) * (k + 1) + l;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let queue = [[0, 0, k]];
seen[id(0, 0, k)] = 1;
let steps = 0;
while (queue.length > 0) {
const next = [];
for (const [r, c, left] of queue) {
if (r === m - 1 && c === n - 1) return steps;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
const nl = left - grid[nr][nc];
if (nl >= 0 && !seen[id(nr, nc, nl)]) {
seen[id(nr, nc, nl)] = 1;
next.push([nr, nc, nl]);
}
}
}
queue = next;
steps++;
}
return -1;
}2Optimal (BFS keeping the most removals per cell)
O(m · n · min(k, m + n))A cell can be re-entered only when its best count strictly rises, so at most min(k, m + n) + 1 times; usually far fewer.O(m · n · min(k, m + n))The best table is m × n; the queue can hold up to one entry per (cell, count) pair in the worst case.Two observations shrink the search. First, a shortest path never steps on more than m + n - 2 cells after the start, so if k >= m + n - 2 the answer is simply m + n - 2. Second, BFS visits states in order of steps, so a later arrival at a cell is only useful if it has more removals left than any earlier one. Keep best[r][c] = most removals left seen at that cell and skip anything that doesn't beat it.
- If k >= m + n - 2, return m + n - 2.
- best[r][c] = -1 everywhere; best[0][0] = k; queue = [(0, 0, k)].
- Process level by level; return the step count when the target is popped.
- For each neighbour: left = cur.left - grid[nr][nc]; if left > best[nr][nc], set best[nr][nc] = left and enqueue.
- If the queue empties, return -1.
class Solution {
public int shortestPath(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
if (k >= m + n - 2) return m + n - 2;
int[][] best = new int[m][n];
for (int[] row : best) Arrays.fill(row, -1);
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
Deque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[] { 0, 0, k });
best[0][0] = k;
int steps = 0;
while (!queue.isEmpty()) {
for (int size = queue.size(); size > 0; size--) {
int[] cur = queue.poll();
if (cur[0] == m - 1 && cur[1] == n - 1) return steps;
for (int[] d : dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
int left = cur[2] - grid[nr][nc];
if (left > best[nr][nc]) {
best[nr][nc] = left;
queue.offer(new int[] { nr, nc, left });
}
}
}
steps++;
}
return -1;
}
}class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
if k >= m + n - 2:
return m + n - 2
best = [[-1] * n for _ in range(m)]
best[0][0] = k
queue = deque([(0, 0, k)])
steps = 0
while queue:
for _ in range(len(queue)):
r, c, left = queue.popleft()
if r == m - 1 and c == n - 1:
return steps
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
nl = left - grid[nr][nc]
if nl > best[nr][nc]:
best[nr][nc] = nl
queue.append((nr, nc, nl))
steps += 1
return -1class Solution {
public:
int shortestPath(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
if (k >= m + n - 2) return m + n - 2;
vector<vector<int>> best(m, vector<int>(n, -1));
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
queue<array<int, 3>> q;
q.push({0, 0, k});
best[0][0] = k;
int steps = 0;
while (!q.empty()) {
for (int size = q.size(); size > 0; size--) {
auto [r, c, left] = q.front();
q.pop();
if (r == m - 1 && c == n - 1) return steps;
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
int nl = left - grid[nr][nc];
if (nl > best[nr][nc]) {
best[nr][nc] = nl;
q.push({nr, nc, nl});
}
}
}
steps++;
}
return -1;
}
};function shortestPath(grid, k) {
const m = grid.length, n = grid[0].length;
if (k >= m + n - 2) return m + n - 2;
const best = Array.from({ length: m }, () => new Array(n).fill(-1));
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let queue = [[0, 0, k]];
best[0][0] = k;
let steps = 0;
while (queue.length > 0) {
const next = [];
for (const [r, c, left] of queue) {
if (r === m - 1 && c === n - 1) return steps;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
const nl = left - grid[nr][nc];
if (nl > best[nr][nc]) {
best[nr][nc] = nl;
next.push([nr, nc, nl]);
}
}
}
queue = next;
steps++;
}
return -1;
}Edge cases to test
- A 1 × 1 grid: you are already there, 0 steps
- k large enough to ignore every wall: the answer is m + n - 2
- Reaching a cell with fewer steps but fewer removals left is not always better than a longer route that saved removals
- k = 0: a plain shortest path that avoids all walls
Hints
Hint 1
Your position alone isn't enough to describe where you are in the search. What else matters for the future?
Hint 2
Run BFS over states (row, col, removals left). Stepping onto a wall uses one removal.
Hint 3
A path never needs more than m + n - 2 removals, and if you've already reached a cell with more removals left, a later visit with fewer left is useless.
FAQ
What is the best time complexity for Shortest Path in a Grid with Obstacles Elimination?
Optimal (BFS keeping the most removals per cell) runs in O(m · n · min(k, m + n)) time and O(m · n · min(k, m + n)) extra space. A cell can be re-entered only when its best count strictly rises, so at most min(k, m + n) + 1 times; usually far fewer.
Which pattern does Shortest Path in a Grid with Obstacles Elimination use?
It is a graphs problem that uses the bfs for shortest path pattern. Other problems with the same pattern: Shortest Path in Binary Matrix, Word Ladder, Bus Routes.
Is there a brute force solution for Shortest Path in a Grid with Obstacles Elimination?
Yes. BFS over (cell, removals left) states takes O(m · n · k) time and O(m · n · k) space. The same cell with a different number of removals left is a different situation, so make it a different node.
Which edge cases should I test for Shortest Path in a Grid with Obstacles Elimination?
A 1 × 1 grid: you are already there, 0 steps; k large enough to ignore every wall: the answer is m + n - 2; Reaching a cell with fewer steps but fewer removals left is not always better than a longer route that saved removals; k = 0: a plain shortest path that avoids all walls.