Shortest Path in a Grid with Obstacles Elimination

Hard Graphs BFS for shortest path Original on LeetCode

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].length
  • 1 <= m, n <= 40
  • 0 <= k <= m * n
  • grid[i][j] is 0 (empty) or 1 (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.

00:00
Testcase

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.

ApproachTimeSpace
BFS over (cell, removals left) statesO(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

TimeO(m · n · k)Each of the m·n·(k+1) states is enqueued at most once and tries 4 moves.
SpaceO(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.

  1. seen[r][c][left] marks visited states. Start with (0, 0, k) at step 0.
  2. Process level by level. When (m - 1, n - 1) is popped, return the step count.
  3. For each of the 4 neighbours inside the grid: newLeft = left - grid[nr][nc].
  4. If newLeft >= 0 and the state is unseen, mark it and enqueue it.
  5. 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;
    }
}

2Optimal (BFS keeping the most removals per cell)

TimeO(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.
SpaceO(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.

  1. If k >= m + n - 2, return m + n - 2.
  2. best[r][c] = -1 everywhere; best[0][0] = k; queue = [(0, 0, k)].
  3. Process level by level; return the step count when the target is popped.
  4. For each neighbour: left = cur.left - grid[nr][nc]; if left > best[nr][nc], set best[nr][nc] = left and enqueue.
  5. 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;
    }
}

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.