Unique Paths II

Problem Description

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 and 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 * 10⁹.

Examples

Constraints

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 ≤ m, n ≤ 100
• obstacleGrid[i][j] is 0 or 1.

State Transition and Space Optimization

Let dp[r][c] be the number of unique paths to reach cell (r, c).

• If grid[r][c] == 1 (obstacle), then dp[r][c] = 0 (cannot reach or pass through this cell).
• Otherwise, dp[r][c] = dp[r - 1][c] + dp[r][c - 1].

Because we only need values from the current row and the row directly above it, we can optimize the space to a 1D array dp of size cols:

• For each cell (r, c):
  • If grid[r][c] == 1, set dp[c] = 0.
  • Else if c > 0, update dp[c] = dp[c] + dp[c - 1] (where dp[c] on the right-hand side represents the value from the row above, and dp[c - 1] represents the value from the current row).

Solution: 1D DP Array

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int rows = obstacleGrid.length;
        int cols = obstacleGrid[0].length;

        // if start or end is blocked, no path exists
        if (obstacleGrid[0][0] == 1 || obstacleGrid[rows - 1][cols - 1] == 1) {
            return 0;
        }

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

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (obstacleGrid[r][c] == 1) {
                    dp[c] = 0;
                } else if (c > 0) {
                    dp[c] += dp[c - 1];
                }
            }
        }

        return dp[cols - 1];
    }
}

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:
        rows, cols = len(obstacleGrid), len(obstacleGrid[0])
        
        if obstacleGrid[0][0] == 1 or obstacleGrid[rows - 1][cols - 1] == 1:
            return 0

        dp = [0] * cols
        dp[0] = 1

        for r in range(rows):
            for c in range(cols):
                if obstacleGrid[r][c] == 1:
                    dp[c] = 0
                elif c > 0:
                    dp[c] += dp[c - 1]

        return dp[-1]

#include <vector>

class Solution {
public:
    int uniquePathsWithObstacles(std::vector<std::vector<int>>& obstacleGrid) {
        int rows = obstacleGrid.size();
        int cols = obstacleGrid[0].size();

        if (obstacleGrid[0][0] == 1 || obstacleGrid[rows - 1][cols - 1] == 1) {
            return 0;
        }

        std::vector<int> dp(cols, 0);
        dp[0] = 1;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (obstacleGrid[r][c] == 1) {
                    dp[c] = 0;
                } else if (c > 0) {
                    dp[c] += dp[c - 1];
                }
            }
        }

        return dp[cols - 1];
    }
};

Complexity Analysis:

• Time Complexity: O(M * N) where M is rows and N is columns.
• Space Complexity: O(N) to store the 1D DP array.

← All Problems