## Table of contents

### No headings in the article.

Hey, so today we are going to solve Leetcode - **Unique Paths II**

**Problem Link-** https://leetcode.com/problems/unique-paths-ii/

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

The code defines a `Solution`

class that encapsulates the logic for calculating the number of unique paths in a grid with obstacles. The main method is `uniquePathsWithObstacles`

, which takes the `obstacleGrid`

as input and returns the number of unique paths.

Here's a step-by-step explanation of the code and its visualization:

The

`uniquePathsWithObstacles`

function initializes the dimensions`m`

and`n`

of the`obstacleGrid`

. It also creates a 2D dynamic programming table`dp`

of size`m x n`

, initialized with zeros.The code checks if the top-left cell

`(0, 0)`

is an obstacle (`obstacleGrid[0][0] == 1`

). If not, it sets`dp[0][0]`

to 1, indicating that there is one unique path to reach the top-left cell.The code fills the first column of the

`dp`

table. Starting from the second row (index 1), for each cell`(i, 0)`

, if it is not an obstacle (`obstacleGrid[i][0] == 0`

), it sets`dp[i][0]`

to the value of the cell above it,`dp[i - 1][0]`

. This indicates that the number of unique paths to reach`(i, 0)`

is the same as the number of unique paths to reach the cell above it.The code fills the first row of the

`dp`

table. Starting from the second column (index 1), for each cell`(0, j)`

, if it is not an obstacle (`obstacleGrid[0][j] == 0`

), it sets`dp[0][j]`

to the value of the cell to its left,`dp[0][j - 1]`

. This indicates that the number of unique paths to reach`(0, j)`

is the same as the number of unique paths to reach the cell to its left.The code iterates through the remaining cells of the

`dp`

table, starting from row 1 and column 1. For each cell`(i, j)`

, if it is not an obstacle (`obstacleGrid[i][j] == 0`

), it calculates the number of unique paths to reach that cell by summing the number of unique paths to reach the cell above it`(i - 1, j)`

and the cell to its left`(i, j - 1)`

. It assigns this value to`dp[i][j]`

.After iterating through all the cells, the value of

`dp[m - 1][n - 1]`

represents the number of unique paths to reach the bottom-right cell of the grid.The function returns

`dp[m - 1][n - 1]`

, which is the number of unique paths in the grid with obstacles.

In summary, the code uses dynamic programming to solve the "Unique Paths II" problem efficiently. It builds a 2D table `dp`

and iteratively fills it by considering each cell's unique paths based on the cells above and to the left. By the end of the process, the bottom-right cell contains the total number of unique paths. This approach avoids redundant calculations and improves the efficiency of the solution.

Note: The code uses a `long long`

data type for the `dp`

table to handle larger grid sizes and avoid integer overflow.