Shortest Path in a Grid with Obstacles Elimination LeetCode Solution

Difficulty Level Hard
Frequently asked in Amazon Apple ByteDance DiDi Facebook Google Microsoft Pinterest Snapchat UberViews 2654

Problem Statement

Shortest Path in a Grid with Obstacles Elimination LeetCode Solution – 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 a walk return -1.

Example

Test Case 1:

Input:

grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]],

k = 1

Output:

6

Shortest Path in a Grid with Obstacles Elimination LeetCode Solution

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).

Approach:

This Problem Sounds difficult at 1st but with some Brainstorming, this problem can be Broken Down into Steps that are easy to understand.

  • Because we are trying to find the shortest path, use BFS here to exit immediately when a path reaches the bottom right-most cell.
  • Use a set to keep track of already visited paths. We only need to keep track of the row, and column, and eliminate obstacle usage count. We don’t need to keep track of the steps because remember we are using BFS for the shortest path. That means there is no value in storing a 4th piece of the data, the current steps. This will reduce the amount of repeat work.
  1. We would use BFS Ideally for Shortest Path Problems & the sam will be Applicable here too. But one thing to note is that we can Eliminate Obstacles to Reach the Target.
  2. Hence we would Push the No of Lives for Further Processing Cells in the Queue. This way we can Segregate and keep the Maximum Lives we can RETAIN up to any cell we will be visiting.
  3. Whenever we encounter an Obstacle we would reduce our lives & Initially Set visited[][] it to -1. This would help us to make sure we only Process cells where lives >= 0.

Code for Shortest Path in a Grid with Obstacles Elimination

Python Program

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        if len(grid) == 1 and len(grid[0]) == 1:
            return 0

        queue = deque([(0,0,k,0)])
        visited = set([(0,0,k)])

        if k > (len(grid)-1 + len(grid[0])-1):
            return len(grid)-1 + len(grid[0])-1

        while queue:
            row, col, eliminate, steps = queue.popleft()
            for new_row, new_col in [(row-1,col), (row,col+1), (row+1, col), (row, col-1)]:
                if (new_row >= 0 and
                    new_row < len(grid) and
                    new_col >= 0 and
                    new_col < len(grid[0])):
                    if grid[new_row][new_col] == 1 and eliminate > 0 and (new_row, new_col, eliminate-1) not in visited:
                        visited.add((new_row, new_col, eliminate-1))
                        queue.append((new_row, new_col, eliminate-1, steps+1))
                    if grid[new_row][new_col] == 0 and (new_row, new_col, eliminate) not in visited:
                        if new_row == len(grid)-1 and new_col == len(grid[0])-1:
                            return steps+1
                        visited.add((new_row, new_col, eliminate))
                        queue.append((new_row, new_col, eliminate, steps+1))

        return -1

Java Program

class Solution {
    public int shortestPath(int[][] grid, int k) {
        int n = grid.length;
        int m = grid[0].length;
        
        if (k >= n+m-2) return m+n-2;
        
        // possible directions
        int[][] directions = new int[][] { {-1,0}, {1,0}, {0,-1}, {0,1} };
        
        // q of [row, col, eliminations used]
        Deque<int[]> q = new ArrayDeque<int[]>();
        
        // visited for each row,col,k
        boolean[][][] visited = new boolean[n][m][k+1];
        
        q.offer(new int[] {0,0,0,0});
        
        while (!q.isEmpty()){
            
            int[] curr = q.poll();
            int row = curr[0], col = curr[1], ks = curr[2], steps = curr[3];
            
            // if its the end, return it
            if (row == n-1 && col == m-1) return steps;
            
            // if already visited this situation, skip
            if (visited[row][col][ks]) continue;
            
            // set this to visited
            visited[row][col][ks] = true;
            
            for (int[] dir : directions) {
                
                int r1 = row+dir[0], c1 = col+dir[1];
                
                if (r1<0 || r1>=n || c1<0 || c1>=m) continue;
                
                if (grid[r1][c1] == 0 && !visited[r1][c1][ks]){
                    q.addLast(new int[] {r1,c1,ks,steps+1} );
                    continue;
                }
                
                if (ks < k && !visited[r1][c1][ks+1]) q.addLast(new int[] {r1,c1,ks+1,steps+1} );
            }
            
        }
        
        return -1;
    }
}

Complexity Analysis for Shortest Path in a Grid with Obstacles Elimination LeetCode Solution

m = rows
n = columns
k = allowed elimination usage

Time Complexity
O(m*n*k) time complexity
This is because for every cell (m*n), in the worst case we have to put that cell into the queue/bfs k times.

Space Complexity
O(m*n*k) space complexity
This is because for every cell (m*n), in the worst case we have to put that cell into the queue/bfs k times which means we need to worst-case store all of those steps/paths in the visited set.

Translate »