Unique Paths II

Medium Subject: 2-D Dynamic Programming

Time Complexity

O(M * N)

Space Complexity

O(M * N)

Problem Description

Problem Statement

You are given an m x n integer array grid. There is a robot initially located at 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 or 0 respectively in grid. Return the number of possible unique paths.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2

Optimal Solution

Python

Approach: Dynamic Programming with Obstacle Handling

Similar to Unique Paths, but if a cell has an obstacle (grid[i][j] == 1), we set dp[i][j] = 0. We must also carefully initialize the first row and column, stopping propagation if an obstacle is encountered.

class Solution:
    def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]

        # Initialize first column
        for i in range(m):
            if grid[i][0] == 1: break
            dp[i][0] = 1

        # Initialize first row
        for j in range(n):
            if grid[0][j] == 1: break
            dp[0][j] = 1

        for i in range(1, m):
            for j in range(1, n):
                if grid[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]