Unique Paths II Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Bloomberg Cisco Cruise Automation Expedia Facebook Google Microsoft Oracle Qualtrics VMware
Array Dynamic Programming MatrixViews 3596

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

Translate »