Shortest Path in a Grid with Obstacles Elimination
HardPrompt
You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.
Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.
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 eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (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: We need to eliminate at least two obstacles to find such a walk.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 401 <= k <= m * ngrid[i][j]is either0or1.grid[0][0] == grid[m - 1][n - 1] == 0
Approaches
2 approaches with complexity analysis and trade-offs.
A* search is an informed search algorithm that improves upon BFS by using a heuristic function to prioritize states that are likely closer to the goal. By exploring more promising paths first, A* can often find the shortest path much faster than an uninformed search like BFS, especially in large search spaces. It is generally the most efficient approach for this type of problem.
Algorithm
-
- Define the state and
visitedarray as in the BFS approach.
- Define the state and
-
- Define a heuristic function,
h(r, c) = (m - 1 - r) + (n - 1 - c), which is the Manhattan distance to the destination.
- Define a heuristic function,
-
- Initialize a priority queue that sorts states based on a priority value. The priority is
steps + heuristic.
- Initialize a priority queue that sorts states based on a priority value. The priority is
-
- Add the initial state to the priority queue:
(heuristic(0,0), 0, 0, 0, k)representing(priority, steps, r, c, rem_k).
- Add the initial state to the priority queue:
-
- Set
visited[0][0] = k.
- Set
-
- While the priority queue is not empty:
- a. Dequeue the state with the lowest priority:
(priority, steps, r, c, rem_k). - b. If
(r, c)is the destination, returnsteps. - c. If a better path to
(r, c)has already been found (i.e.,visited[r][c] > rem_k), skip this state. - d. For each of the 4 neighbors
(nr, nc):- i. If the neighbor is valid, calculate
next_k = rem_k - grid[nr][nc]. - ii. If
next_k >= 0andvisited[nr][nc] < next_k:- iii. Update
visited[nr][nc] = next_k. - iv. Calculate the new priority:
new_priority = (steps + 1) + h(nr, nc). - v. Enqueue the new state
(new_priority, steps + 1, nr, nc, next_k).
- iii. Update
- i. If the neighbor is valid, calculate
-
- If the loop finishes, no path was found. Return -1.
Walkthrough
The core idea of A* is to use a priority queue to explore states. The priority of a state is determined by the function f(s) = g(s) + h(s), where:
g(s)is the cost to reach statesfrom the start. Here, it's the number ofsteps.h(s)is a heuristic estimate of the cost from statesto the goal. A perfect heuristic for a grid is the Manhattan distance:h(row, col) = (m - 1 - row) + (n - 1 - col). This heuristic is admissible (it never overestimates the actual cost), which guarantees that A* will find the optimal path.
The state representation (row, col, remaining_k) and the visited array optimization are the same as in the BFS approach. The only difference is the use of a priority queue ordered by steps + heuristic instead of a regular queue.
import java.util.Arrays;import java.util.PriorityQueue; class Solution { public int shortestPath(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; if (k >= m + n - 2) { return m + n - 2; } // Priority Queue for A*: {priority, steps, r, c, rem_k} // priority = steps + manhattan_distance PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // visited[r][c] = max remaining k to reach this cell int[][] visited = new int[m][n]; for (int i = 0; i < m; i++) { Arrays.fill(visited[i], -1); } // Heuristic for starting point int initialHeuristic = m - 1 + n - 1; pq.offer(new int[]{initialHeuristic, 0, 0, 0, k}); // priority, steps, r, c, rem_k visited[0][0] = k; int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; while (!pq.isEmpty()) { int[] current = pq.poll(); // int priority = current[0]; int steps = current[1]; int r = current[2]; int c = current[3]; int rem_k = current[4]; if (r == m - 1 && c == n - 1) { return steps; } // If we have found a better path to this cell, skip if (visited[r][c] > rem_k) { continue; } for (int[] dir : directions) { int nr = r + dir[0]; int nc = c + dir[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n) { int next_k = rem_k - grid[nr][nc]; if (next_k >= 0 && visited[nr][nc] < next_k) { visited[nr][nc] = next_k; int newHeuristic = m - 1 - nr + n - 1 - nc; int newPriority = steps + 1 + newHeuristic; pq.offer(new int[]{newPriority, steps + 1, nr, nc, next_k}); } } } } return -1; }}Complexity
Time
O(m * n * k * log(m * n * k)). The `log` factor comes from the priority queue operations. The size of the priority queue can be up to `O(m * n * k)`. In practice, it's often much faster than BFS because it explores fewer states.
Space
O(m * n * k). The priority queue can hold up to `O(m * n * k)` states in the worst case. The `visited` array takes `O(m * n)` space.
Trade-offs
Pros
More efficient on average than BFS because the heuristic intelligently guides the search towards the goal.
Guaranteed to find the shortest path due to the use of an admissible heuristic.
Cons
Slightly more complex to implement than BFS due to the priority queue and heuristic calculation.
The worst-case time complexity has an additional logarithmic factor compared to BFS, although it's faster in practice.
This problem can be modeled as a shortest path problem on a graph. Since all edge weights (steps) are 1, Breadth-First Search (BFS) is a suitable algorithm. The standard BFS explores a 2D grid, but here we have an additional constraint: the ability to eliminate k obstacles. This means the "state" of our search is not just the cell's coordinates (row, col), but also the number of obstacles we can still eliminate, k.
Algorithm
-
- Define a state as a tuple
(row, col, remaining_k), representing being at cell(row, col)withremaining_kobstacle eliminations left.
- Define a state as a tuple
-
- Initialize a queue for BFS and add the starting state:
(0, 0, k, 0), where the last element is the number of steps.
- Initialize a queue for BFS and add the starting state:
-
- Use a 2D array
visited[m][n]to store the maximumremaining_kwith which we have reached cell(row, col). Initialize all its values to -1.
- Use a 2D array
-
- Mark the starting cell as visited:
visited[0][0] = k.
- Mark the starting cell as visited:
-
- While the queue is not empty, dequeue the current state
(r, c, rem_k, steps).
- While the queue is not empty, dequeue the current state
-
- If
(r, c)is the destination(m-1, n-1), returnstepsas this is the shortest path.
- If
-
- For each of the four neighbors
(nr, nc):
- a. Check if the neighbor is within the grid boundaries.
- b. Calculate the remaining eliminations after moving to the neighbor:
next_k = rem_k - grid[nr][nc]. - c. If
next_k >= 0(we can make the move) ANDvisited[nr][nc] < next_k(this is a better way to reach this cell), then:- i. Update
visited[nr][nc] = next_k. - ii. Enqueue the new state
(nr, nc, next_k, steps + 1).
- i. Update
- For each of the four neighbors
-
- If the queue becomes empty and the destination has not been reached, it's impossible to find a path. Return -1.
Walkthrough
We define a state by the cell's coordinates and the remaining obstacle elimination capacity: (row, col, remaining_k). The BFS algorithm explores the grid layer by layer, guaranteeing that the first time we reach the destination, it will be via the shortest path.
To avoid cycles and redundant computations, we use a visited array. A simple boolean visited[m][n] is insufficient because we might find a better path to a cell if we arrive with more elimination capacity. Therefore, we use a 2D array visited[m][n] to store the maximum remaining_k we have reached cell (row, col) with. If we reach the same cell again with a smaller or equal remaining_k, we know that path is not better, so we can prune it.
An initial optimization can be made: if k is large enough to clear a path along the grid's perimeter (Manhattan distance), the shortest path is simply m + n - 2. This occurs when k >= m + n - 2.
import java.util.Arrays;import java.util.LinkedList;import java.util.Queue; class Solution { public int shortestPath(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; // Optimization: if k is large enough, the shortest path is the Manhattan distance if (k >= m + n - 2) { return m + n - 2; } Queue<int[]> queue = new LinkedList<>(); // state: {row, col, remaining_k, steps} queue.offer(new int[]{0, 0, k, 0}); // visited[row][col] = max remaining_k to reach this cell int[][] visited = new int[m][n]; for (int i = 0; i < m; i++) { Arrays.fill(visited[i], -1); } visited[0][0] = k; int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; while (!queue.isEmpty()) { int[] current = queue.poll(); int r = current[0]; int c = current[1]; int rem_k = current[2]; int steps = current[3]; if (r == m - 1 && c == n - 1) { return steps; } for (int[] dir : directions) { int nr = r + dir[0]; int nc = c + dir[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n) { int next_k = rem_k - grid[nr][nc]; if (next_k >= 0 && visited[nr][nc] < next_k) { visited[nr][nc] = next_k; queue.offer(new int[]{nr, nc, next_k, steps + 1}); } } } } return -1; }}Complexity
Time
O(m * n * k). In the worst case, we might have to visit each cell `(r, c)` with every possible value of `remaining_k` from `0` to `k`. Each state is processed once.
Space
O(m * n * k). The queue can hold up to `O(m * n * k)` states in the worst case. The `visited` array takes `O(m * n)` space.
Trade-offs
Pros
Guaranteed to find the shortest path because it explores layer by layer.
Conceptually straightforward extension of standard BFS.
Correct and passes within time limits for the given constraints.
Cons
Can be slow if the grid or
kis large, as it explores many states that might be far from the goal.The space complexity can be high, potentially storing
m * n * kstates in the queue.
Solutions
Solution
class Solution {public int shortestPath(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; if (k >= m + n - 3) { return m + n - 2; } Deque<int[]> q = new ArrayDeque<>(); q.offer(new int[]{0, 0, k}); boolean[][][] vis = new boolean[m][n][k + 1]; vis[0][0][k] = true; int ans = 0; int[] dirs = {-1, 0, 1, 0, -1}; while (!q.isEmpty()) { ++ans; for (int i = q.size(); i > 0; --i) { int[] p = q.poll(); k = p[2]; for (int j = 0; j < 4; ++j) { int x = p[0] + dirs[j]; int y = p[1] + dirs[j + 1]; if (x >= 0 && x < m && y >= 0 && y < n) { if (x == m - 1 && y == n - 1) { return ans; } if (grid[x][y] == 0 && !vis[x][y][k]) { q.offer(new int[]{x, y, k}); vis[x][y][k] = true; } else if (grid[x][y] == 1 && k > 0 && !vis[x][y][k - 1]) { q.offer(new int[]{x, y, k - 1}); vis[x][y][k - 1] = true; } } } } } return -1; }}class Solution {public: int shortestPath(vector<vector<int>> &grid, int k) { int m = grid.size(), n = grid[0].size(); if (k >= m + n - 3) return m + n - 2; queue<vector<int>> q; q.push({0, 0, k}); vector<vector<vector<bool>>> vis( m, vector<vector<bool>>(n, vector<bool>(k + 1))); vis[0][0][k] = true; int ans = 0; vector<int> dirs = {-1, 0, 1, 0, -1}; while (!q.empty()) { ++ans; for (int i = q.size(); i > 0; --i) { auto p = q.front(); k = p[2]; q.pop(); for (int j = 0; j < 4; ++j) { int x = p[0] + dirs[j], y = p[1] + dirs[j + 1]; if (x >= 0 && x < m && y >= 0 && y < n) { if (x == m - 1 && y == n - 1) return ans; if (grid[x][y] == 0 && !vis[x][y][k]) { q.push({x, y, k}); vis[x][y][k] = true; } else if (grid[x][y] == 1 && k > 0 && !vis[x][y][k - 1]) { q.push({x, y, k - 1}); vis[x][y][k - 1] = true; } } } } } 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 - 3: return m + n - 2 q = deque([(0, 0, k)]) vis = {(0, 0, k)} ans = 0 while q: ans += 1 for _ in range(len(q)): i, j, k = q . popleft() for a, b in [[0, - 1], [0, 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n: if x == m - 1 and y == n - 1: return ans if grid[x][y] == 0 and (x, y, k) not in vis: q . append((x, y, k)) vis . add((x, y, k)) if grid[x][y] == 1 and k > 0 and (x, y, k - 1) not in vis: q . append((x, y, k - 1)) vis . add((x, y, k - 1)) return - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.