Unique Paths II Leetcode Problem 63 [Python Solution]

Lets get solving the Unique Paths II problem, which is a medium-level challenge falling under the category of 2-D Dynamic Programming.

The problem presents a scenario where you are given an M x N grid, and your goal is to calculate the number of unique paths a robot can take from the top-left corner to the bottom-right corner.

The robot can only move down or to the right at any given point in time, and certain grid cells are blocked with obstacles (marked as 1) while others are open spaces (marked as 0).

Your task is to find the number of valid paths, considering the obstacles, and return this count.

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 3×3 grid.

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.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

Understanding Unique Paths II Constraints

To efficiently solve the Unique Paths II problem, it’s important to understand the constraints involved.

These constraints guide our approach to finding a solution:

• The grid dimensions are between 1×1 and 100×100, which means we can have grids of various sizes.
• The robot can only move down or to the right, ensuring a straightforward path.
• Obstacles are marked as 1, which restricts movement through specific grid cells.

Unique Paths II LeetCode Problem Solution

Now, let’s explore the solutions to this problem.

We’ll discuss a Bruteforce Approach followed by a more Efficient Approach using Dynamic Programming (DP).

1. Bruteforce Approach

The most straightforward way to tackle this problem is through recursion and a depth-first search (DFS) approach.

We’ll start from the top-left corner and recursively explore both down and right directions, counting the number of unique paths.

Here’s a Python code snippet demonstrating the Bruteforce Approach:

def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
    M, N = len(grid), len(grid[0])

    # Recursive DFS function
    def dfs(r, c):
        # Base cases:
        if r == M or c == N or grid[r][c]:
            return 0
        if r == M - 1 and c == N - 1:
            return 1

        # Recursive exploration
        return dfs(r + 1, c) + dfs(r, c + 1)

    return dfs(0, 0)

This solution is simple to understand and implement but becomes inefficient for larger grids with many obstacles.

To optimize the solution, we can use Dynamic Programming.

2. An Efficient Approach with Dynamic Programming

Dynamic Programming is an effective technique for optimizing problems like this.

It eliminates redundant computations by storing and reusing previously calculated results.

For this problem, we can use a 2D DP array to keep track of the number of unique paths for each cell.

Here’s a Python code snippet demonstrating the Efficient DP Approach:

View on GitHub ➹
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        M, N = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * N for _ in range(M)]

        # Initialize the bottom-right cell
        dp[M-1][N-1] = 1

        # Iterate through the grid in reverse order
        for r in reversed(range(M)):
            for c in reversed(range(N)):
                if obstacleGrid[r][c]:
                    dp[r][c] = 0
                else:
                    if r + 1 < M:
                        dp[r][c] += dp[r + 1][c]
                    if c + 1 < N:
                        dp[r][c] += dp[r][c + 1]

        return dp[0][0]