Last updated on March 2nd, 2025 at 05:01 pm
Here, we see a Unique Paths II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Dynamic Programming
Companies
Bloomberg
Level of Question
Medium
Unique Paths II LeetCode Solution
Table of Contents
1. Problem Statement
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 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:
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Dynamic Programming”. The problem is solved by breaking it into smaller subproblems and using a 2D dp table to store intermediate results, avoiding redundant calculations.
3. Code Implementation in Different Languages
3.1 Unique Paths II C++
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid[0][0] == 1) return 0;
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n,0));
dp[0][0] = 1;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (obstacleGrid[i][j] == 1 || (i == 0 && j == 0)) continue;
else dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);
return dp[m-1][n-1];
}
};
3.2 Unique Paths II Java
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid[0][0] == 1) return 0;
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = 1;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (obstacleGrid[i][j] == 1 || (i == 0 && j == 0)) continue;
else dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);
return dp[m-1][n-1];
}
}
3.3 Unique Paths II JavaScript
var uniquePathsWithObstacles = function(obstacleGrid) {
if (obstacleGrid[0][0]) return 0
let m = obstacleGrid.length, n = obstacleGrid[0].length
let dp = Array.from({length: m}, el => new Uint32Array(n))
dp[0][0] = 1
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (obstacleGrid[i][j] || (!i && !j)) continue
else dp[i][j] = (i ? dp[i-1][j] : 0) + (j ? dp[i][j-1] : 0)
return dp[m-1][n-1]
};
3.4 Unique Paths II Python
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
if not obstacleGrid:
return
r, c = len(obstacleGrid), len(obstacleGrid[0])
dp = [[0 for _ in xrange(c)] for _ in xrange(r)]
dp[0][0] = 1 - obstacleGrid[0][0]
for i in xrange(1, r):
dp[i][0] = dp[i-1][0] * (1 - obstacleGrid[i][0])
for i in xrange(1, c):
dp[0][i] = dp[0][i-1] * (1 - obstacleGrid[0][i])
for i in xrange(1, r):
for j in xrange(1, c):
dp[i][j] = (dp[i][j-1] + dp[i-1][j]) * (1 - obstacleGrid[i][j])
return dp[-1][-1]
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(m * n) | O(m * n) |
| Java | O(m * n) | O(m * n) |
| JavaScript | O(m * n) | O(m * n) |
| Python | O(m * n) | O(m * n) |
- The code uses bottom-up dynamic programming to solve the problem.
- The
dptable ensures that each subproblem is solved only once, making the solution efficient. - The obstacle check ensures that paths through blocked cells are not considered.