Unique Paths II

Dynamic Programming2D Matrix

25 min

Problem Statement

You are given an m x n integer array grid. There is a robot on the top-left corner. The robot tries to move to the bottom-right corner. 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 the grid. Return the number of unique paths that the robot can take to reach the bottom-right corner.

Example

Example 1:

Output: 2

Solution

This problem is a variation of "Unique Paths" with the addition of obstacles. We can use a similar dynamic programming approach, but we need to handle the obstacles.

If a cell `(i, j)` contains an obstacle, the number of paths to reach it is 0. This will naturally propagate through the DP grid, as any path that would have used this cell is now invalid.

Algorithm Steps (DP)

If the starting cell `(0,0)` has an obstacle, no paths are possible, so return 0.
Create an `m x n` DP grid. Initialize `dp[0][0]` to 1.
Handle the first row and column: if a cell has an obstacle, all subsequent cells in that row/column are unreachable (0 paths). Otherwise, they have 1 path.
Iterate through the rest of the grid from `(1, 1)`.
If `grid[i][j]` is an obstacle, set `dp[i][j] = 0`.
Otherwise, `dp[i][j] = dp[i-1][j] + dp[i][j-1]`.
The final answer is `dp[m-1][n-1]`.

Unique Paths II DP Grid

Progress1 / 1

Ready to start.

Unique Paths II (DP)


class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        
        if obstacleGrid[0][0] == 1:
            return 0
            
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1
        
        for i in range(1, m):
            dp[i][0] = int(obstacleGrid[i][0] == 0 and dp[i-1][0] == 1)
            
        for j in range(1, n):
            dp[0][j] = int(obstacleGrid[0][j] == 0 and dp[0][j-1] == 1)
            
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                    
        return dp[m-1][n-1]