Problem Statement: Unique Paths II
You are given a m x n grid, where each cell can either be obstacle (1) or empty (0). You start at the top-left corner (0, 0) and you need to find how many unique paths exist to reach the bottom-right corner (m-1, n-1). You can only move right or down at any point in time.
If there is an obstacle at the destination or at the starting point, return 0 as no path is possible.
Example 1:
Input:
grid = [
[0,0,0],
[0,1,0],
[0,0,0]
]
Output:
2
Explanation: There are two unique paths:
- Right → Right → Down → Down
- Down → Down → Right → Right
Example 2:
Input:
grid = [
[0,1],
[0,0]
]
Output:
1
Explanation: There is only one unique path: Down → Right.
Approach:
This problem is a variation of the Unique Paths problem, but it introduces obstacles into the grid. We will use Dynamic Programming (DP) to solve it.
Dynamic Programming Approach:
- State Definition:
- Let
dp[i][j]represent the number of unique paths to reach the cell(i, j)from the top-left corner(0, 0).
- Let
- State Transition:
- If the cell
(i, j)contains an obstacle (i.e.,grid[i][j] == 1), thendp[i][j] = 0because no path can pass through it. - Otherwise, the number of unique paths to
(i, j)is the sum of the number of unique paths from the cell above it(i-1, j)and the cell to the left of it(i, j-1): dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1]
- If the cell
- Base Cases:
dp[0][0] = 1ifgrid[0][0]is not an obstacle, since there’s only one way to be at the starting point.- For the first row (
dp[0][j]), if any cell contains an obstacle, all subsequent cells in that row will havedp[0][j] = 0. - For the first column (
dp[i][0]), similarly, if any cell contains an obstacle, all subsequent cells in that column will havedp[i][0] = 0.
- Final Answer:
- The final answer is the value in
dp[m-1][n-1], which gives the number of unique paths to the bottom-right corner.
- The final answer is the value in
Time and Space Complexity:
- Time Complexity: O(m * n), where
mandnare the dimensions of the grid. We need to iterate through each cell of the grid. - Space Complexity: O(m * n) for storing the DP table. We can optimize it to O(n) by using a 1D array to store the results of the current row.
Code Implementations in Different Languages:
1. C Language (DP Approach):
#include <stdio.h>
int uniquePathsWithObstacles(int** obstacleGrid, int m, int n) {
int dp[n];
// Initialize the first row
dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
for (int j = 1; j < n; j++) {
dp[j] = obstacleGrid[0][j] == 1 ? 0 : dp[j-1];
}
// Fill in the rest of the grid
for (int i = 1; i < m; i++) {
dp[0] = obstacleGrid[i][0] == 1 ? 0 : dp[0];
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
} else {
dp[j] += dp[j-1];
}
}
}
return dp[n-1];
}
int main() {
int m = 3, n = 3;
int grid[3][3] = {
{0,0,0},
{0,1,0},
{0,0,0}
};
int* obstacleGrid[3] = {grid[0], grid[1], grid[2]};
printf("Unique Paths: %d\n", uniquePathsWithObstacles(obstacleGrid, m, n));
return 0;
}
2. C++ Language (DP Approach):
#include <iostream>
#include <vector>
using namespace std;
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<int> dp(n, 0);
// Initialize the first row
dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
for (int j = 1; j < n; j++) {
dp[j] = obstacleGrid[0][j] == 1 ? 0 : dp[j-1];
}
// Fill in the rest of the grid
for (int i = 1; i < m; i++) {
dp[0] = obstacleGrid[i][0] == 1 ? 0 : dp[0];
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
} else {
dp[j] += dp[j-1];
}
}
}
return dp[n-1];
}
int main() {
vector<vector<int>> grid = {
{0, 0, 0},
{0, 1, 0},
{0, 0, 0}
};
cout << "Unique Paths: " << uniquePathsWithObstacles(grid) << endl; // Output: 2
return 0;
}
3. Java (DP Approach):
public class UniquePathsII {
public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[] dp = new int[n];
dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
for (int j = 1; j < n; j++) {
dp[j] = obstacleGrid[0][j] == 1 ? 0 : dp[j - 1];
}
for (int i = 1; i < m; i++) {
dp[0] = obstacleGrid[i][0] == 1 ? 0 : dp[0];
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
} else {
dp[j] += dp[j - 1];
}
}
}
return dp[n - 1];
}
public static void main(String[] args) {
int[][] grid = {
{0, 0, 0},
{0, 1, 0},
{0, 0, 0}
};
System.out.println("Unique Paths: " + uniquePathsWithObstacles(grid)); // Output: 2
}
}
4. Python (DP Approach):
def uniquePathsWithObstacles(grid):
m = len(grid)
n = len(grid[0])
dp = [0] * n
dp[0] = 1 if grid[0][0] == 0 else 0
for j in range(1, n):
dp[j] = 0 if grid[0][j] == 1 else dp[j-1]
for i in range(1, m):
dp[0] = 0 if grid[i][0] == 1 else dp[0]
for j in range(1, n):
if grid[i][j] == 1:
dp[j] = 0
else:
dp[j] += dp[j-1]
return dp[-1]
# Test case
grid = [
[0, 0, 0],
[0, 1, 0],
[0, 0, 0]
]
print("Unique Paths:", uniquePathsWithObstacles(grid)) # Output: 2
5. C# (DP Approach):
using System;
class Program {
public static int UniquePathsWithObstacles(int[,] obstacleGrid) {
int m = obstacleGrid.GetLength(0);
int n = obstacleGrid.GetLength(1);
int[] dp = new int[n];
dp[0] = obstacleGrid[0, 0] == 1 ? 0 : 1;
for (int j = 1; j < n; j++) {
dp[j] = obstacleGrid[0, j] == 1 ? 0 : dp[j - 1];
}
for (int i = 1; i < m; i++) {
dp[0] = obstacleGrid[i, 0] == 1 ? 0 : dp[0];
for (int j = 1; j < n; j++) {
if (obstacleGrid[i, j] == 1) {
dp[j] = 0;
} else {
dp[j] += dp[j - 1];
}
}
}
return dp[n - 1];
}
static void Main() {
int[,] grid = {
{0, 0, 0},
{0, 1, 0},
{0, 0, 0}
};
Console.WriteLine("Unique Paths: " + UniquePathsWithObstacles(grid)); // Output: 2
}
}
6. JavaScript (DP Approach):
function uniquePathsWithObstacles(grid) {
let m = grid.length;
let n = grid[0].length;
let dp = new Array(n).fill(0);
dp[0] = grid[0][0] === 1 ? 0 : 1;
for (let j = 1; j < n; j++) {
dp[j] = grid[0][j] === 1 ? 0 : dp[j-1];
}
for (let i = 1; i < m; i++) {
dp[0] = grid[i][0] === 1 ? 0 : dp[0];
for (let j = 1; j < n; j++) {
if (grid[i][j] === 1) {
dp[j] = 0;
} else {
dp[j] += dp[j-1];
}
}
}
return dp[n-1];
}
// Test case
const grid = [
[0, 0, 0],
[0, 1, 0],
[0, 0, 0]
];
console.log("Unique Paths:", uniquePathsWithObstacles(grid)); // Output: 2
Complexity Analysis:
Time Complexity:
- Time Complexity: O(m * n), where
mis the number of rows andnis the number of columns in the grid. We process each cell exactly once. - Space Complexity: O(n), where
nis the number of columns, since we optimize the space by using only a 1D array to store the number of ways to reach each cell.
Conclusion:
This problem can be efficiently solved using Dynamic Programming by filling up a DP table with the number of unique paths at each cell, while handling obstacles appropriately. The approach ensures that we find the number of unique paths even when obstacles are present in the grid.