63. Unique Paths II LeetCode Solution

In this guide, you will get 63. Unique Paths II LeetCode Solution with the best time and space complexity. The solution to Unique Paths II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Unique Paths II solution in C++
Unique Paths II solution in Java
Unique Paths II solution in Python
Additional Resources

63. Unique Paths II LeetCode Solution image

Problem Statement of Unique Paths II

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:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3×3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

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.

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

63. Unique Paths II LeetCode Solution in C++

class Solution {
 public:
  int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    const int m = obstacleGrid.size();
    const int n = obstacleGrid[0].size();
    // dp[i][j] := the number of unique paths from (0, 0) to (i, j)
    vector<vector<long>> dp(m + 1, vector<long>(n + 1, 0));
    dp[0][1] = 1;  // Can also set dp[1][0] = 1.

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        if (!obstacleGrid[i - 1][j - 1])
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

    return dp[m][n];
  }
};
/* code provided by PROGIEZ */

63. Unique Paths II LeetCode Solution in Java

class Solution {
  public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    final int m = obstacleGrid.length;
    final int n = obstacleGrid[0].length;
    // dp[i][j] := the number of unique paths from (0, 0) to (i, j)
    long[][] dp = new long[m + 1][n + 1];
    dp[0][1] = 1; // Can also set dp[1][0] = 1.

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

    return (int) dp[m][n];
  }
}
// code provided by PROGIEZ

63. Unique Paths II LeetCode Solution in Python

class Solution:
  def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:
    m = len(obstacleGrid)
    n = len(obstacleGrid[0])
    # dp[i][j] := the number of unique paths from (0, 0) to (i, j)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    dp[0][1] = 1  # Can also set dp[1][0] = 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]

    return dp[m][n]
 # code by PROGIEZ