Unique Paths II Leetcode Solution

Problem Statement

The Unique Paths II LeetCode Solution – “Unique Paths II” states that given the m x n grid where a robot starts from the top left corner of the grid. We need to find the total number of ways to reach the bottom right corner of the grid.

A cell containing an obstacle contains 1 while, 0 for a free cell.

Example:

Input:  obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

Output: 2

Explanation:

• There exists an obstacle in the middle of the grid.
• There exists exactly 2 unique paths to reach from the top-left corner to bottom right corner of the matrix.
  • Right, Right, Down, Down.
  • Down, Down, Right, Right.

Input: obstacleGrid = [[0,1],[0,0]]

Output: 1

Explanation:

• There is exactly 1 unique path.
  • Down, Right.
• Hence, 1 is our answer.

Approach

Idea:

1. The main idea to solve this problem is to use dynamic programming.
2. Let dp[i][j] = number of unique paths ending at this cell.
3. If the current cell contains an obstacle, dp[i][j] = 0.
4. If the current cell is a free cell:
   1. We can reach the current cell from the top cell, hence dp[i][j] += dp[i-1][j], provided the top cell exists.
   2. We can reach the current cell from the left cell, hence dp[i][j] += dp[i][j-1], provided the left cell exists.
5. Finally, our answer is dp[n-1][m-1].

Code

Unique Paths II Leetcode C++ Solution:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(),m = obstacleGrid.back().size();
        vector<vector<int>> dp(n,vector<int>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i==0 and j==0){
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = 1;
                    }
                }
                else if(i==0){
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = dp[i][j-1];
                    }
                }
                else if(j==0){
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = dp[i-1][j];
                    }
                }
                else{
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    }
                }
            }
        }
        return dp[n-1][m-1];
    }
};

Unique Paths II Leetcode Java Solution:

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[][] dp = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i==0 && j==0){
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = 1;
                    }
                }
                else if(i==0){
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = dp[i][j-1];
                    }
                }
                else if(j==0){
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = dp[i-1][j];
                    }
                }
                else{
                    if(obstacleGrid[i][j]==0){
                        dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    }
                }
            }
        }
        return dp[n-1][m-1];
    }
}

Complexity Analysis for Unique Paths II Leetcode Solution

Time Complexity

The time complexity of the above code is O(N*M) where N = number of rows and M = number of columns.

Since we traversed the entire input matrix at least once, Time Complexity is O(N*M).

Space Complexity

The space complexity of the above code is O(N*M). We need a dynamic programming matrix of size N*M to store all intermediate values.

Reference: https://en.wikipedia.org/wiki/Dynamic_programming