Nayan PahujaHello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-14.
DAY 14 Problem: Grid Unique Paths II
You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The testcases are generated so that the answer will be less than or equal to 2 * 109.
Example 1:
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
- Right -> Right -> Down -> Down
- Down -> Down -> Right -> Right
Intuition:
In most of the matrix problems, an iterative solution is harder to form and imagine right out of the gate.
Here through observation we can narrow this question into merely 3 choices.
Go Down/Go Right/return back to starting position cos there is an obstacle.
That's it. and That is what we are going to attempt. We are trying to write a recursive code to implement this.
Approach: Recursion
- We know that our recursive solution must have a base case/break case where it returns the final value.
- Here if we reach the end of our matrix, we shall return 1 for confirmed path.
- Now we have two options either to go down or go right.
- And we will call a recursive function and leave that as it is.
Code:
class Solution {
public:
int uniquePathsHelper(int i, int j, int m, int n, vector<vector<int>>& obstacleGrid)
{
//base case/reached end of the matrix
if( i == m-1 && j == n-1)
return 1;
int paths = 0;
if(i < m-1 && obstacleGrid[i][j] != 1 )
{
paths += uniquePathsHelper(i + 1, j, m, n,obstacleGrid); // Move down
}
if(j < n-1 && obstacleGrid[i][j] != 1 )
{
paths += uniquePathsHelper(i, j+1, m, n,obstacleGrid); // Move down
}
return paths;
}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
//extreme case
if(obstacleGrid[m-1][n-1] == 1)
{
return 0;
}
return uniquePathsHelper(0,0,m,n,obstacleGrid);
}
};
Complexity Analysis:
Time Complexity: O(2^(N+M))
Space Complexity: O(N-1) + O(M-1)
Ouch. That's a lot of time complexity. We should try to reduce it else we will fail a lot of testcases.
Let's try applying DP here. Since we can observe that here there are multiple overlapping sub routes to the end, We can simply store them in a matrix and call them from that.
Approach: Memoization + Recursion
- Create a DP array of size [m][n]
- Whenever we want to find the answer of a particular row and column (say helper(i,j)), we first check whether the answer is already calculated using the dp array(i.e dp[i][j]!= -1 ). If yes, simply return the value from the dp array.
- Else we will use the recursive relation as usual but before returning from the function, we will set dp[i][j] to the solution we get.
Code:
int uniquePathsHelper(int i, int j, int m, int n, vector<vector<int>>& obstacleGrid, vector<vector<int>>& dp)
{
//base case/reached end of the matrix
int down = 0, right =0;
if( i == m-1 && j == n-1)
return 1;
// checking dp
if(dp[i][j] != -1)
{
return dp[i][j];
}
if(i < m-1 && obstacleGrid[i][j] != 1 )
{
down += uniquePathsHelper(i + 1, j, m, n,obstacleGrid,dp); // Move down
}
if(j < n-1 && obstacleGrid[i][j] != 1 )
{
right += uniquePathsHelper(i, j+1, m, n,obstacleGrid,dp); // Move right
}
return dp[i][j] = down+right;
}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n,-1));
//extreme case
if(obstacleGrid[m-1][n-1] == 1)
{
return 0;
}
return uniquePathsHelper(0,0,m,n,obstacleGrid,dp);
}
Complexity Analysis:
Time Complexity: O(N*M))
Space Complexity: O(N-1) + O(M-1) + O(N*M).
Explanation: Extra Space O(M*N) is used by the DP array.
Approach: Tabulation DP
We can further optimize it's space complexity by elimination of recursive stack using the tabulation approach.
Here The Tabulation base case is dp[0][0] = 1.
Our answer should get stored in dp[m-1][n-1]. We want to move from (0,0) to (m-1,n-1). We should move such that at a particular i and j, we have all the values required to compute dp[i][j].
We can use two nested loops to have this traversal.
Whenever i>0 , j>0 and mat[i][j]==-1, we will simply mark dp[i][j] = 0, because it's a blocked path.
Code:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n, -1));
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
int up, left = 0;
if(i >= 0 && j >= 0 && obstacleGrid[i][j] == 1) dp[i][j] = 0;
else if(i == 0 && j == 0) dp[i][j] = 1;
else {
if(i > 0) up = dp[i-1][j];
if(j > 0) left = dp[i][j-1];
dp[i][j] = up + left;
}
}
}
return dp[m-1][n-1];
}
Complexity Analysis:
Time Complexity: O(N*M))
Space Complexity: O(N*M).
Explanation: Space O(M*N) is used by the DP array.
That is all for normal DP approaches.
We can further reduce it's space complexity , because if we carefully observe we only required the previous row at a time. Hence there is no need to store the full matrix but store the necessary values in dp[j] vector.
Thanks for reading. Feedback is highly appreciated.
