DAY 14 - Grid Unique Paths II

Nayan Pahuja - Jun 17 '23 - - Dev Community

Hello 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:

  1. Right -> Right -> Down -> Down
  2. Down -> Down -> Right -> Right

Matrix

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);
    }
};
Enter fullscreen mode Exit fullscreen mode

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);
    }
Enter fullscreen mode Exit fullscreen mode

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];
    }
Enter fullscreen mode Exit fullscreen mode

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.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .