# Unique Paths II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/unique-paths-ii)
Canonical: https://scaleengineer.com/dsa/problems/unique-paths-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Agoda](https://scaleengineer.com/companies/agoda), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Atlassian](https://scaleengineer.com/companies/atlassian), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cisco](https://scaleengineer.com/companies/cisco), [Flipkart](https://scaleengineer.com/companies/flipkart), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [athenahealth](https://scaleengineer.com/companies/athenahealth), [Coupang](https://scaleengineer.com/companies/coupang), [Zepto](https://scaleengineer.com/companies/zepto), [Zomato](https://scaleengineer.com/companies/zomato), [Pinterest](https://scaleengineer.com/companies/pinterest), [Cruise](https://scaleengineer.com/companies/cruise)
---
## Problem
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:**

![](https://assets.glich.co/dsa/unique-paths-ii/image0.jpg) 

**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

**Example 2:**

![](https://assets.glich.co/dsa/unique-paths-ii/image1.jpg) 

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

**Constraints:**

* `m == obstacleGrid.length`
* `n == obstacleGrid[i].length`
* `1 <= m, n <= 100`
* `obstacleGrid[i][j]` is `0` or `1`.

# Approaches
## Brute-Force Recursion
This approach directly translates the problem into a recursive function. For any given cell, the number of paths is the sum of paths from the cell below and the cell to the right. We explore all possible paths from the start to the end, but this leads to an exponential number of redundant calculations.
**Time:** O(2^(m+n)) · **Space:** O(m + n)
**Pros:** Simple to understand and implement.; Directly translates the problem's recursive nature.
**Cons:** Extremely inefficient due to recomputing the same subproblems.; Will result in a "Time Limit Exceeded" (TLE) error for larger grids.
### Explanation
We define a recursive helper function, say `countPaths(row, col)`, which calculates the number of unique paths from the current cell `(row, col)` to the destination `(m-1, n-1)`. The function has the following logic:

*   **Base Cases:**
    *   If the current cell `(row, col)` is an obstacle (`obstacleGrid[row][col] == 1`), no paths can pass through it, so we return 0.
    *   If the current cell is the destination `(m-1, n-1)`, we have found one valid path, so we return 1.
    *   If the current cell is out of the grid boundaries, it's an invalid path, so we return 0.
*   **Recursive Step:**
    *   For any other cell, the number of paths is the sum of the paths from moving down (`countPaths(row + 1, col)`) and the paths from moving right (`countPaths(row, col + 1)`).

The initial call to the function will be `countPaths(0, 0)`. This method is simple but highly inefficient because it recalculates the number of paths for the same cells multiple times.

```java
public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        // Need to handle the case where the destination itself is an obstacle
        if (obstacleGrid[m - 1][n - 1] == 1) return 0;
        return countPaths(0, 0, m, n, obstacleGrid);
    }

    private int countPaths(int row, int col, int m, int n, int[][] obstacleGrid) {
        // If out of bounds or on an obstacle, there are no paths.
        if (row >= m || col >= n || obstacleGrid[row][col] == 1) {
            return 0;
        }

        // If we reached the destination, we found one path.
        if (row == m - 1 && col == n - 1) {
            return 1;
        }

        // Recursively find paths by moving down and right.
        int pathsDown = countPaths(row + 1, col, m, n, obstacleGrid);
        int pathsRight = countPaths(row, col + 1, m, n, obstacleGrid);

        return pathsDown + pathsRight;
    }
}
```
### Algorithm
1. Define a recursive function `solve(row, col, grid)`.
2. Check for base cases:
   a. If `row` or `col` are out of bounds, or if `grid[row][col] == 1`, return 0.
   b. If `row` and `col` point to the destination `(m-1, n-1)`, return 1.
3. Recursively call the function for the next possible moves:
   a. `paths_down = solve(row + 1, col, grid)`
   b. `paths_right = solve(row, col + 1, grid)`
4. Return the sum `paths_down + paths_right`.
5. The main function calls `solve(0, 0, obstacleGrid)`.

## Recursion with Memoization (Top-Down DP)
This approach optimizes the brute-force recursion by using a memoization table (a 2D array) to store the results of subproblems. This technique, also known as top-down dynamic programming, avoids redundant computations for the same cell, drastically improving performance.
**Time:** O(m*n) · **Space:** O(m*n)
**Pros:** Much more efficient than brute-force recursion.; Avoids TLE for the given constraints.; Maintains a clear, top-down recursive structure.
**Cons:** Uses O(m*n) extra space for the memoization table.; Can lead to stack overflow for very deep recursion, though not an issue for the given constraints.
### Explanation
We enhance the recursive solution by adding a cache, typically a 2D array `memo`, of the same dimensions as the grid. `memo[i][j]` will store the number of unique paths from cell `(i, j)` to the destination.

The `memo` table is initialized with a special value (e.g., -1) to indicate that a state has not been computed yet. In the recursive function `countPaths(row, col)`, before any computation, we first check if `memo[row][col]` has a value other than -1. If it does, we return the stored value directly. Otherwise, we compute the result as in the brute-force approach, and before returning, we store the result in `memo[row][col]`. This ensures that the number of paths for each cell is calculated only once.

```java
public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] memo = new int[m][n];
        for (int[] row : memo) {
            java.util.Arrays.fill(row, -1);
        }
        // Need to handle the case where the destination itself is an obstacle
        if (obstacleGrid[m - 1][n - 1] == 1) return 0;
        return countPaths(0, 0, m, n, obstacleGrid, memo);
    }

    private int countPaths(int row, int col, int m, int n, int[][] obstacleGrid, int[][] memo) {
        if (row >= m || col >= n || obstacleGrid[row][col] == 1) {
            return 0;
        }
        if (row == m - 1 && col == n - 1) {
            return 1;
        }
        if (memo[row][col] != -1) {
            return memo[row][col];
        }

        int pathsDown = countPaths(row + 1, col, m, n, obstacleGrid, memo);
        int pathsRight = countPaths(row, col + 1, m, n, obstacleGrid, memo);

        memo[row][col] = pathsDown + pathsRight;
        return memo[row][col];
    }
}
```
### Algorithm
1. Create a 2D array `memo` of size `m x n` and initialize all its values to -1.
2. Define a function `solve(row, col, grid, memo)`.
3. Check for base cases:
   a. If `row` or `col` are out of bounds, or if `grid[row][col] == 1`, return 0.
   b. If `row` and `col` point to the destination `(m-1, n-1)`, return 1.
4. Check the memoization table: If `memo[row][col]` is not -1, return its value.
5. Recursively call the function for the next possible moves:
   a. `paths_down = solve(row + 1, col, grid, memo)`
   b. `paths_right = solve(row, col + 1, grid, memo)`
6. Store the result `paths_down + paths_right` in `memo[row][col]`.
7. Return the stored result.
8. The main function calls `solve(0, 0, obstacleGrid, memo)`.

## 2D Dynamic Programming (Bottom-Up)
This is an iterative, bottom-up dynamic programming approach. We use a 2D DP table to store the number of unique paths to reach each cell. The value of a cell `(i, j)` is calculated based on the sum of paths to the cell above `(i-1, j)` and the cell to its left `(i, j-1)`.
**Time:** O(m*n) · **Space:** O(m*n)
**Pros:** Efficient and avoids recursion overhead.; Generally faster in practice than memoization due to being iterative.
**Cons:** Requires O(m*n) extra space, which can be optimized.
### Explanation
We create a 2D array `dp` of size `m x n`, where `dp[i][j]` will store the number of unique paths from the start `(0, 0)` to the cell `(i, j)`. The state transition is `dp[i][j] = dp[i-1][j] + dp[i][j-1]`.

*   **Initialization:**
    *   First, check if the start cell is an obstacle. If `obstacleGrid[0][0] == 1`, no path is possible, so return 0.
    *   Set `dp[0][0] = 1` as there is one way to be at the starting cell.
    *   Initialize the first row: For `j` from 1 to `n-1`, `dp[0][j]` can only be reached from `dp[0][j-1]`. If `obstacleGrid[0][j]` is an obstacle or `dp[0][j-1]` is 0, then `dp[0][j]` is 0. Otherwise, it's 1.
    *   Initialize the first column similarly.
*   **Iteration:**
    *   Iterate from `i = 1` to `m-1` and `j = 1` to `n-1`.
    *   For each cell `(i, j)`, if it's an obstacle (`obstacleGrid[i][j] == 1`), set `dp[i][j] = 0`.
    *   Otherwise, calculate `dp[i][j] = dp[i-1][j] + dp[i][j-1]`.

The final result is the value in the bottom-right cell of the DP table, `dp[m-1][n-1]`.

```java
public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        int[][] dp = new int[m][n];
        dp[0][0] = 1;

        // Fill first column
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 0 && dp[i - 1][0] == 1) {
                dp[i][0] = 1;
            } else {
                dp[i][0] = 0;
            }
        }

        // Fill first row
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] == 0 && dp[0][j - 1] == 1) {
                dp[0][j] = 1;
            } else {
                dp[0][j] = 0;
            }
        }

        // Fill the rest of the grid
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}
```
### Algorithm
1. Get grid dimensions `m` and `n`.
2. If `obstacleGrid[0][0] == 1`, return 0.
3. Create a 2D DP array `dp[m][n]`.
4. Set `dp[0][0] = 1`.
5. Fill the first column: For `i` from 1 to `m-1`, `dp[i][0] = (obstacleGrid[i][0] == 0 && dp[i-1][0] == 1) ? 1 : 0`.
6. Fill the first row: For `j` from 1 to `n-1`, `dp[0][j] = (obstacleGrid[0][j] == 0 && dp[0][j-1] == 1) ? 1 : 0`.
7. Iterate from `i = 1` to `m-1` and `j = 1` to `n-1`:
   a. If `obstacleGrid[i][j] == 1`, set `dp[i][j] = 0`.
   b. Else, `dp[i][j] = dp[i-1][j] + dp[i][j-1]`.
8. Return `dp[m-1][n-1]`.

## Space-Optimized 1D Dynamic Programming
This approach optimizes the 2D DP solution's space complexity. Since calculating the number of paths for the current row only requires values from the current and previous row, we can use a single 1D array to store the DP values, reducing space from `O(m*n)` to `O(n)`.
**Time:** O(m*n) · **Space:** O(n)
**Pros:** Highly efficient in both time and space.; Optimal space complexity among solutions that do not modify the input.
**Cons:** The logic can be slightly less intuitive than the 2D DP approach.; The 1D array is overwritten, so we lose the path counts for previous rows.
### Explanation
We use a 1D array `dp` of size `n`. `dp[j]` will represent the number of paths to reach the cell in the current row at column `j`.

We iterate through the grid row by row. For each row `i`, we update the `dp` array. The update rule `dp[j] = dp[j] + dp[j-1]` works because when we are at `(i, j)`, `dp[j]` still holds the value from the previous row `(i-1, j)`, and `dp[j-1]` has just been updated to hold the value for `(i, j-1)`.

*   **Initialization:**
    *   Create a `dp` array of size `n`.
    *   If `obstacleGrid[0][0] == 1`, return 0. Otherwise, set `dp[0] = 1`.
*   **Iteration:**
    *   Iterate through rows `i` from 0 to `m-1`.
    *   For each row, iterate through columns `j` from 0 to `n-1`.
    *   If `obstacleGrid[i][j] == 1`, there are no paths to this cell, so set `dp[j] = 0`.
    *   If `j > 0`, add the paths from the left cell: `dp[j] += dp[j-1]`.
    *   Note: For the first cell of each row (`j=0`), if it's an obstacle, `dp[0]` becomes 0. If not, it retains its value from the previous row, which is correct as it can only be reached from above.

```java
public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        int[] dp = new int[n];
        dp[0] = 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                } else if (j > 0) {
                    dp[j] = dp[j] + dp[j - 1];
                }
            }
        }

        return dp[n - 1];
    }
}
```
### Algorithm
1. Get grid dimensions `m` and `n`.
2. If `obstacleGrid[0][0] == 1`, return 0.
3. Create a 1D DP array `dp` of size `n`.
4. Initialize `dp[0] = 1`.
5. Iterate through rows `i` from 0 to `m-1`:
   a. Iterate through columns `j` from 0 to `n-1`:
      i. If `obstacleGrid[i][j] == 1`, set `dp[j] = 0`.
      ii. Else if `j > 0`, update `dp[j] = dp[j] + dp[j-1]`.
6. Return `dp[n-1]`.

## In-place Dynamic Programming
This is the most space-efficient approach, using the input grid itself as the DP table. It modifies the grid to store the number of paths to each cell, thus achieving O(1) extra space complexity. This is feasible if modifying the input is allowed.
**Time:** O(m*n) · **Space:** O(1)
**Pros:** Most space-efficient solution with O(1) extra space.; Maintains the optimal O(m*n) time complexity.
**Cons:** Modifies the input array, which might be undesirable in some contexts.; The logic for handling the first row/column and distinguishing obstacles from path counts can be tricky to implement correctly.
### Explanation
The core idea is to use the `obstacleGrid` to store the DP values. A cell `obstacleGrid[i][j]` is updated to hold the number of unique paths to reach it. This eliminates the need for any auxiliary data structure.

1.  First, we handle the starting cell `(0,0)`. If it's an obstacle (value 1), no path is possible, so we return 0. Otherwise, we set `obstacleGrid[0][0] = 1` to signify one way to reach the start (by starting there).
2.  Next, we process the first column. A cell `(i, 0)` is reachable only if it's not an obstacle and the cell above it `(i-1, 0)` was reachable. We update `obstacleGrid[i][0]` to 1 if these conditions hold, and 0 otherwise.
3.  We do the same for the first row. A cell `(0, j)` is reachable only if it's not an obstacle and the cell to its left `(0, j-1)` was reachable.
4.  Finally, we iterate through the rest of the grid. For any cell `(i, j)`, if it's an obstacle, the number of paths to it is 0. Otherwise, it's the sum of paths from the cell above (`obstacleGrid[i-1][j]`) and the cell to the left (`obstacleGrid[i][j-1]`).
5.  The final answer is the value stored in the bottom-right cell, `obstacleGrid[m-1][n-1]`.

```java
public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        // If the starting cell has an obstacle, then simply return 0
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        // Number of ways of reaching the starting cell = 1
        obstacleGrid[0][0] = 1;

        // Filling the values for the first column
        for (int i = 1; i < m; i++) {
            obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0;
        }

        // Filling the values for the first row
        for (int j = 1; j < n; j++) {
            obstacleGrid[0][j] = (obstacleGrid[0][j] == 0 && obstacleGrid[0][j - 1] == 1) ? 1 : 0;
        }

        // Starting from cell(1,1) fill up the values
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                } else {
                    obstacleGrid[i][j] = 0;
                }
            }
        }

        // Return value stored in rightmost bottommost cell.
        return obstacleGrid[m - 1][n - 1];
    }
}
```
### Algorithm
1. Get grid dimensions `m` and `n`.
2. If `obstacleGrid[0][0] == 1`, return 0.
3. Set `obstacleGrid[0][0] = 1` (to represent 1 path).
4. Fill the first column: For `i` from 1 to `m-1`, set `obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i-1][0] == 1) ? 1 : 0`.
5. Fill the first row: For `j` from 1 to `n-1`, set `obstacleGrid[0][j] = (obstacleGrid[0][j] == 0 && obstacleGrid[0][j-1] == 1) ? 1 : 0`.
6. Iterate from `i = 1` to `m-1` and `j = 1` to `n-1`:
   a. If `obstacleGrid[i][j] == 1` (original obstacle), set its path count to 0.
   b. Else, `obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]`.
7. Return `obstacleGrid[m-1][n-1]`.

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @param {number[][]} obstacleGrid * @return {number} */ var uniquePathsWithObstacles =
  function (obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const f = Array.from({ length: m }, () => Array(n).fill(-1));
    const dfs = (i, j) => {
      if (i >= m || j >= n || obstacleGrid[i][j] === 1) {
        return 0;
      }
      if (i === m - 1 && j === n - 1) {
        return 1;
      }
      if (f[i][j] === -1) {
        f[i][j] = dfs(i + 1, j) + dfs(i, j + 1);
      }
      return f[i][j];
    };
    return dfs(0, 0);
  };

```

### CPP

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

```

### Python

```python
class Solution:
    # dp[1][1] = dp[0][1] + dp[1][0] # so, set either dp[0][1]=1, or set dp[1][0]=1 dp [ 0 ][ 1 ] = 1 for i in range ( 1 , m + 1 ): for j in range ( 1 , n + 1 ): if obstacleGrid [ i - 1 ][ j - 1 ] == 0 : dp [ i ][ j ] = dp [ i - 1 ][ j ] + dp [ i ][ j - 1 ] # else, ==1, obstacle, skip and leave as 0 return dp [ m ][ n ] ############ class Solution : def uniquePathsWithObstacles ( self , obstacleGrid : List [ List [ int ]]) -> int : m , n = len ( obstacleGrid ), len ( obstacleGrid [ 0 ]) dp = [[ 0 ] * n for _ in range ( m )] for i in range ( m ): if obstacleGrid [ i ][ 0 ] == 1 : break dp [ i ][ 0 ] = 1 for j in range ( n ): if obstacleGrid [ 0 ][ j ] == 1 : break dp [ 0 ][ j ] = 1 for i in range ( 1 , m ): for j in range ( 1 , n ): if obstacleGrid [ i ][ j ] == 0 : dp [ i ][ j ] = dp [ i - 1 ][ j ] + dp [ i ][ j - 1 ] return dp [ - 1 ][ - 1 ]
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: if not obstacleGrid: return 0 m, n = len(obstacleGrid), len(obstacleGrid[0]) dp = [[0] * (n + 1) for _ in range(m + 1)]

```