Shortest Path in a Grid with Obstacles Elimination

HARD

Description

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

Approaches

Checkout 2 different approaches to solve Shortest Path in a Grid with Obstacles Elimination. Click on different approaches to view the approach and algorithm in detail.

A* Search Algorithm

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

1. Define the state and visited array as in the BFS approach.
1. Define a heuristic function, h(r, c) = (m - 1 - r) + (n - 1 - c), which is the Manhattan distance to the destination.
1. Initialize a priority queue that sorts states based on a priority value. The priority is steps + heuristic.
1. Add the initial state to the priority queue: (heuristic(0,0), 0, 0, 0, k) representing (priority, steps, r, c, rem_k).
1. Set visited[0][0] = k.
1. 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, return steps.
- 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 >= 0 and visited[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).
1. If the loop finishes, no path was found. Return -1.

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 state s from the start. Here, it's the number of steps.
h(s) is a heuristic estimate of the cost from state s to 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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Shortest Path in a Grid with Obstacles Elimination. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Shortest Path in a Grid with Obstacles Elimination

Algorithms:

Breadth-First Search

Data Structures:

ArrayMatrix

Companies:

Snap |Databricks |Pinterest |Nuro |