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.
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; }}Video 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.