Leetcode Shortest Path in a Grid with Obstacles Elimination

Question

I am getting TLE error for bigger input grid size. How can I improve to resolve it? I am using backtracking here.

Given a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.

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. class Solution {

int min= Integer.MAX_VALUE;

public int shortestPath(int[][] grid, int k) {
    
    
    helper(grid,0,0,0,0,k);
    return min==Integer.MAX_VALUE?-1:min;
    
    
}

void helper(int grid[][],int x, int y, int step, int obstacles,int k){
    if(x<0 || y<0 || x>=grid.length || y>=grid[0].length || obstacles>k || grid[x][y]>1){

        return; 
    }
    
    if(x==grid.length-1 && y==grid[0].length-1){
        min = Math.min(min,step);
        return;
    }
    if(grid[x][y]==1) obstacles++;
    int temp = grid[x][y];
    grid[x][y]=2;
    helper(grid,x+1,y,step+1,obstacles,k);
    helper(grid,x,y+1,step+1,obstacles,k);
    helper(grid,x-1,y,step+1,obstacles,k);
    helper(grid,x,y-1,step+1,obstacles,k);
    grid[x][y]=temp;
}

}

Anyone Help?

Answer 1

Looks pretty good so far!

• We'd probably want to check for visited nodes.

---

This'd pass using a Queue and LinkedList:

import java.util.Queue;
import java.util.LinkedList;

public class Solution {
    static final int[][] directions = new int[][] {{0, 1}, {1, 0}, { -1, 0}, {0, -1}};
    public static final int shortestPath(
        final int[][] grid,
        final int k
    ) {
        final int rowLength = grid.length;
        final int colLength = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][][] visited = new boolean[rowLength][colLength][k + 1];
        visited[0][0][0] = true;
        queue.offer(new int[] {0, 0, 0});
        int minSteps = 0;

        while (!queue.isEmpty()) {
            final int size = queue.size();

            for (int i = 0; i < size; i++) {
                final int[] info = queue.poll();
                final int row = info[0];
                final int col = info[1];
                final int currObstacble = info[2];

                if (row == rowLength - 1 && col == colLength - 1) {
                    return minSteps;
                }

                for (int[] direction : directions) {
                    final int nextRow = direction[0] + row;
                    final int nextCol = direction[1] + col;
                    int nextObstacle = currObstacble;

                    if (nextRow > -1 && nextRow < rowLength && nextCol > -1 && nextCol < colLength) {
                        if (grid[nextRow][nextCol] == 1) {
                            nextObstacle++;
                        }

                        if (nextObstacle <= k && !visited[nextRow][nextCol][nextObstacle]) {
                            visited[nextRow][nextCol][nextObstacle] = true;
                            queue.offer(new int[] {nextRow, nextCol, nextObstacle});
                        }
                    }
                }
            }

            minSteps++;
        }

        return -1;
    }
}