# Unique Paths II Leetcode Solution

Difficulty Level Medium
Array Dynamic Programming MatrixViews 2579

## 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.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.

Translate »