Algorithm
Problem Name: 63. Unique Paths II
Problem Link: https://leetcode.com/problems/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 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
Constraints:
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]is0or1.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
int uniquePathsWithObstacles(int **obstacleGrid, int m, int n){
int (*p)[n] = (int (*)[n]) calloc(m * n, sizeof(int));
p[0][0] = 1;
int i, j;
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
if (obstacleGrid[i][j]) {
p[i][j] = 0;
}
else {
if (i > 0 && j == 0)
p[i][j] = p[i - 1][j];
if (j > 0 && i == 0)
p[i][j] = p[i][j - 1];
if (i > 0 && j > 0)
p[i][j] = p[i][j - 1] + p[i - 1][j];
}
}
}
return p[m - 1][n - 1];
}
int main(){
int m, n, i;
m = n = 3;
int **obstacleGrid = (int **) calloc (m, sizeof(int *));
for (i = 0; i < m; i++)
obstacleGrid[i] = (int *) calloc (n, sizeof(int));
obstacleGrid[1][1] = 1;
printf("%d\n", uniquePathsWithObstacles(obstacleGrid, m, n));
return 0;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
vector<int>dp(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 {
dp[j] += dp[j - 1];
}
}
}
return dp[n - 1];
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
for (int i=0; i < dp.length; i++) {
if (obstacleGrid[i][0] == 1) {
break;
}
dp[i][0] = 1;
}
for (int i=0; i < dp[0].length; i++) {
if (obstacleGrid[0][i] == 1) {
break;
}
dp[0][i] = 1;
}
for (int i=1; i < dp.length; i++) {
for (int j=1; j < dp[0].length; j++) {
if (obstacleGrid[i][j] != 1) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[obstacleGrid.length-1][obstacleGrid[0].length-1];
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const uniquePathsWithObstacles = function(obstacleGrid) {
const rows = obstacleGrid.length
const cols = obstacleGrid[0].length
const dp = Array.from({ length: rows }, () => new Array(cols).fill(0))
if (obstacleGrid[0][0] === 1) return 0
else dp[0][0] = 1
let firstRowOneIdx
let firstColOneIdx
for (let i = 0; i < cols; i++) {
if (obstacleGrid[0][i] === 1) {
firstRowOneIdx = i
break
} else {
dp[0][i] = 1
}
}
for (let i = 0; i < rows; i++) {
if (obstacleGrid[i][0] === 1) {
firstColOneIdx = i
break
} else {
dp[i][0] = 1
}
}
for (let i = 1; i < rows; i++) {
for (let j = 1; j < cols; j++) {
if (obstacleGrid[i][j] !== 1) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
}
}
}
return dp[rows - 1][cols - 1]
}
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid):
if obstacleGrid[0][0] == 1: return 0
for i in range(len(obstacleGrid)):
for j in range(len(obstacleGrid[0])):
if obstacleGrid[i][j] == 1 or i == j == 0:
obstacleGrid[i][j] -= 1
else:
add1 = obstacleGrid[i - 1][j] if i > 0 else 0
add2 = obstacleGrid[i][j - 1] if j > 0 else 0
obstacleGrid[i][j] += add1 + add2
return abs(obstacleGrid[-1][-1])
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _063_UniquePaths2
{
public int UniquePathsWithObstacles(int[,] obstacleGrid)
{
var rowLenght = obstacleGrid.GetLength(0);
var columnLenght = obstacleGrid.GetLength(1);
if (rowLenght < = columnLenght)
{
var possiblePath = new int[rowLenght];
possiblePath[0] = obstacleGrid[0, 0] == 0 ? 1 : 0;
for (int i = 0; i < columnLenght; i++)
for (int j = 0; j < rowLenght; j++)
possiblePath[j] = obstacleGrid[j, i] == 1
? 0
: j != 0 ? possiblePath[j - 1] + possiblePath[j] : possiblePath[j];
return possiblePath[rowLenght - 1];
}
else
{
var possiblePath = new int[columnLenght];
possiblePath[0] = obstacleGrid[0, 0] == 0 ? 1 : 0;
for (int i = 0; i < rowLenght; i++)
for (int j = 0; j < columnLenght; j++)
possiblePath[j] = obstacleGrid[i, j] == 1
? 0
: j != 0 ? possiblePath[j - 1] + possiblePath[j] : possiblePath[j];
return possiblePath[columnLenght - 1];
}
}
}
}
Input
Output