Shortest Path in a Grid with Obstacles Elimination
Problem
m x n grid of 0 (empty) and 1
(wall) cells and may step up, down, left or right. Walking into a wall is allowed only by
destroying it, and you may destroy at most k walls in total. Return the
minimum number of steps from the top-left to the bottom-right corner, or -1 if it
cannot be done.grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1Output6grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1Output-1grid = [[0,1],[1,0]], k = 1Output21 ≤ m, n ≤ 40 · 1 ≤ k ≤ m·n · grid[0][0] = grid[m-1][n-1] = 0
Try it yourself
class Solution {
public int shortestPath(int[][] grid, int k) {
}
}
k ≥ m+n-3
the straight Manhattan path is always possible, and a cell revisited with no more
walls-left than before can be skipped.Instinct Minimum moves, fewest steps or shortest transformation where every step costs the same: spread outward level by level with a queue.
Memory hack Ripples in a pond: every ring is one step farther, so the first ring that touches the target is the answer.
Open the Graph BFS guide →Approaches
Brute ForceBacktracking over Simple Paths
O(3m·n)Space O(m·n)DFS from the start, never revisiting a cell on the current path, spending one elimination per wall entered. Record the shortest length that reaches the corner and prune branches already as long as the best. Every simple path may be explored.
private int best; public int shortestPath(int[][] grid, int k) { best = Integer.MAX_VALUE; dfs(grid, 0, 0, k, 0, new boolean[grid.length][grid[0].length]); return best == Integer.MAX_VALUE ? -1 : best; } private void dfs(int[][] g, int r, int c, int left, int steps, boolean[][] onPath) { if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || onPath[r][c]) return; if (g[r][c] == 1) { if (left == 0) return; left--; // smash this wall } if (steps >= best) return; if (r == g.length - 1 && c == g[0].length - 1) { best = steps; return; } onPath[r][c] = true; dfs(g, r + 1, c, left, steps + 1, onPath); dfs(g, r - 1, c, left, steps + 1, onPath); dfs(g, r, c + 1, left, steps + 1, onPath); dfs(g, r, c - 1, left, steps + 1, onPath); onPath[r][c] = false; }
Exponential — fine as a correctness oracle on tiny grids only.
BetterBFS over (row, col, walls left)
O(m·n·k)Space O(m·n·k)Treat each (r, c, left) triple as a node and BFS level by level; the
first time the corner is dequeued, the level is the answer. Entering a wall moves to
left - 1. A 3-D seen array ensures each state is processed
once.
public int shortestPath(int[][] grid, int k) { int m = grid.length, n = grid[0].length; boolean[][][] seen = new boolean[m][n][k + 1]; int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1}; Deque<int[]> queue = new ArrayDeque<>(); queue.offer(new int[]{0, 0, k}); seen[0][0][k] = true; for (int steps = 0; !queue.isEmpty(); steps++) { 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 = 0; d < 4; d++) { int r = cur[0] + dr[d], c = cur[1] + dc[d]; if (r < 0 || c < 0 || r >= m || c >= n) continue; int left = cur[2] - grid[r][c]; if (left < 0 || seen[r][c][left]) continue; seen[r][c][left] = true; queue.offer(new int[]{r, c, left}); } } } return -1; }
Polynomial and correct, but k can be up to m·n, so the state space is huge.
OptimalBFS with Manhattan Shortcut + Best-Remaining Pruning
O(m·n·min(k, m+n))Space O(m·n·min(k, m+n))An L-shaped path has only m+n-3 interior cells, so with that many
eliminations the answer is simply m+n-2. Otherwise k < m+n, and we keep
bestLeft[r][c]: a later BFS visit with no more walls left is dominated by an
earlier one (fewer or equal steps), so it is dropped.
public int shortestPath(int[][] grid, int k) { int m = grid.length, n = grid[0].length; if (k >= m + n - 3) return m + n - 2; // bulldoze a straight L-shaped route int[][] bestLeft = new int[m][n]; // most walls-left seen on arrival for (int[] row : bestLeft) Arrays.fill(row, -1); bestLeft[0][0] = k; int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1}; Deque<int[]> queue = new ArrayDeque<>(); queue.offer(new int[]{0, 0, k}); for (int steps = 0; !queue.isEmpty(); steps++) { 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 = 0; d < 4; d++) { int r = cur[0] + dr[d], c = cur[1] + dc[d]; if (r < 0 || c < 0 || r >= m || c >= n) continue; int left = cur[2] - grid[r][c]; if (left <= bestLeft[r][c]) continue; // dominated (or negative) bestLeft[r][c] = left; queue.offer(new int[]{r, c, left}); } } } return -1; }
Caps k at m+n and stores one integer per cell — the accepted approach.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Backtracking over Simple Paths | O(3m·n) | O(m·n) |
| Better | BFS over (row, col, walls left) | O(m·n·k) | O(m·n·k) |
| Optimal | BFS with Manhattan Shortcut + Best-Remaining Pruning | O(m·n·min(k, m+n)) | O(m·n·min(k, m+n)) |
- Using a 2-D visited array — a cell reached with more eliminations left must be revisitable.
- Charging an elimination for the start or end cell (both are guaranteed empty).
- Allocating
[m][n][k+1]without capping k — k can be 1600.
- Name the trick: “BFS with augmented state” (position + resource left).
- Bring up the
k ≥ m+n-3shortcut — interviewers love the observation. - Contrast with Dijkstra: all moves cost 1, so plain BFS already gives shortest steps.