1293. Shortest Path in a Grid with Obstacles Elimination
Problem Solving - Day 30
Hello, reader 👋🏽 ! Welcome to day 30 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.
Today, I will be picking up LeetCode's daily challenge problem: 1293. Shortest Path in a Grid with Obstacles Elimination.
🤔 Problem Statement
- There is an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle).
- The allowed moves are: 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 at most k obstacles can be eliminated. - If it is not possible to find such walk return -1.
- E.g.:
grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1=>-1grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1=>6
💬 Thought Process - DFS
- This seems like a problem where you try to visit all the possible ways around grid from
0,0tom-1,n-1while trying all possible ways to eliminate at most k obstacles. - As you might have realised, walking through all such possible paths will be costly and exponential.
- We can try reducing this run time by using recursion, memoization and backtracking.
At every cell, we have the following options:
- If the cell has an obstacle (1), and
k=0, that is you cannot eliminate any obstacle, then returnMAX_VALUEas this path is blocked. - If the cell has an obstacle (1) and
k != 0, then you can eliminate this obstacle and try visiting top, left, bottom, and right if those cells are unvisited. - If the cell is empty, then all possible paths can be explored if unvisited.
- If the cell has an obstacle (1), and
We will have to separately have a visited array that keeps track of the visited cells along one particular path to avoid revisiting.
- Let's look into the code now.
👩🏽💻 Solution - DFS
class Solution {
public int shortestPath(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
boolean[][][] visited = new boolean[m][n][k+1];
int[][][] memo = new int[m][n][k+1];
for(int[][] row1: memo) {
for(int[] row2: row1) {
Arrays.fill(row2, -1);
}
}
int ans = shortestPathHelper(m-1, n-1, grid, k, visited, memo);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
private int shortestPathHelper(int i, int j, int[][] grid, int k, boolean[][][] visited, int[][][] memo) {
int m = grid.length, n = grid[0].length;
// You reached destination
if(i == 0 && j == 0) {
return 0;
}
// If this cell was already visited along this path, then go back
if(visited[i][j][k]) {
return Integer.MAX_VALUE;
}
// If path from this cell to destination was already computed, return the answer
if(memo[i][j][k] != -1) {
return memo[i][j][k];
}
// mark the cell visited
visited[i][j][k] = true;
int left = Integer.MAX_VALUE,
right = Integer.MAX_VALUE,
down = Integer.MAX_VALUE,
top = Integer.MAX_VALUE;
int curr = grid[i][j];
// If the cell has an obstacle and you can eliminate no more obstacles,
// then this path is blocked
if(curr == 1 && k == 0) {
return memo[i][j][k] = Integer.MAX_VALUE;
}
int l = j-1;
int r = j+1;
int t = i-1;
int d = i+1;
// If the index is in bounds,
// then call the child depending on whether
// the current cell is empty or has an obstacle that can be eliminated
if(l >= 0) {
if(curr == 0)
left = shortestPathHelper(i, l, grid, k, visited, memo);
if(curr == 1) {
// remove this obstacle and also check
left = Math.min(left, shortestPathHelper(i, l, grid, k-1, visited, memo));
}
}
if(r < n) {
if(curr == 0)
right = shortestPathHelper(i, r, grid, k, visited, memo);
if(curr == 1 ) {
// remove this obstacle and also check
right = Math.min(right, shortestPathHelper(i, r, grid, k-1, visited, memo));
}
}
if(t >= 0) {
if(curr == 0)
top = shortestPathHelper(t, j, grid, k, visited, memo);
if(curr == 1) {
// remove this obstacle and also check
top = Math.min(top, shortestPathHelper(t, j, grid, k-1, visited, memo));
}
}
if(d < m) {
if(curr == 0)
down = shortestPathHelper(d, j, grid, k, visited, memo);
if(curr == 1) {
// remove this obstacle and also check
down = Math.min(down, shortestPathHelper(d, j, grid, k-1, visited, memo));
}
}
// Compute the minimum of all 4 directions
int iMin = Math.min(top, down);
int jMin = Math.min(right, left);
int min = Math.min(iMin, jMin);
if(min != Integer.MAX_VALUE) {
min += 1;
}
// memoize the value and return
visited[i][j][k] = false;
return memo[i][j][k] = min;
}
}
Time Complexity: O(n * m * k)
- n = number of rows
- m = number of columns
- k = number of obstacles that can be removed
Space Complexity: O(n * m * k)
- n = number of rows
- m = number of columns
- k = number of obstacles that can be removed
- There is additional stack space as well.
💬 Thought Process - BFS
- Since the questions asks for the minimum number of steps and all the steps have equal weights, we can be smart and use the BFS shortest path to return the path with minimum steps.
- We will use a queue and keep adding the cell indices
(i,j), the remaining obstacles that can be removed and the steps it took to reach there. - We will also use a visited array to avoid visited the same cell when k obstacles remain.
- The code is straightforward BFS with an additional check when polling if the destination has been reached, as well as checking if the cell is an obstacle and no more can be removed.
👩🏽💻 Solution - BFS
class Block {
// The cell indices, remaining obstacles to be removed,
// steps it took to reach there
int row, col, k, step;
Block(int row, int col, int k, int step) {
this.row = row;
this.col = col;
this.k = k;
this.step = step;
}
}
class Solution {
public int shortestPath(int[][] grid, int k) {
Queue<Block> queue = new LinkedList();
// 4 directions, (up, down, left, right)
int[][] directions = new int[][] {
{-1,0}, {1,0}, {0,-1}, {0,1}
};
int m = grid.length, n = grid[0].length;
boolean[][][] visited = new boolean[m][n][k+1];
Block t = new Block(0, 0, k, 0);
queue.add(t);
visited[0][0][k] = true;
while(!queue.isEmpty()) {
Block front = queue.poll();
int row = front.row;
int col = front.col;
int removals = front.k;
int step = front.step;
// If you've reached destination return true
if(row == m-1 && col == n-1) {
return step;
}
int curr = grid[row][col];
if(curr == 1) {
if(removals == 0) {
// you can no longer move down this path
continue;
}
else {
removals -= 1;
}
}
for(int[] dir: directions) {
int nRow = row + dir[0];
int nCol = col + dir[1];
int newStep = step + 1;
// If the indices are invalid or the cell has already been visited
if(nRow < 0 || nCol < 0 || nRow >= m || nCol >= n || visited[nRow][nCol][removals]) {
continue;
}
Block child = new Block(nRow, nCol, removals, newStep);
visited[nRow][nCol][removals] = true;
queue.add(child);
}
}
return -1;
}
}
Time Complexity: O(n * m * k)
- n = number of rows
- m = number of columns
- k = number of obstacles that can be removed
Space Complexity: O(n * m * k)
- n = number of rows
- m = number of columns
- k = number of obstacles that can be removed
- You can find the code for this question in the GitHub repo here: 1293. Shortest Path in a Grid with Obstacles Elimination.
Conclusion
That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!
Thank you for reading!