NUHMAN.com

Introduction

LeetCode 63: Unique Paths II is a variation of the classic Unique Paths problem. In this version, the grid contains obstacles, which means that some cells cannot be traversed. The problem asks us to find the number of unique paths from the top-left corner to the bottom-right corner, where obstacles are present.

The challenge lies in handling obstacles effectively while counting the paths, which requires dynamic programming. The problem also introduces the concept of obstacle grids, where some cells are blocked, and the path counting must consider these obstacles.

Problem Statement

A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. However, some cells in the grid are obstacles (represented by 1), and others are free spaces (represented by 0).

How many possible unique paths are there to reach the bottom-right corner, considering obstacles?

Example 1:

go

Input: obstacleGrid = [
    [0,0,0],
    [0,1,0],
    [0,0,0]
]
Output: 2
Explanation: There are two ways to reach the bottom-right corner:
1. Right → Right → Down → Down
2. Down → Down → Right → Right

Example 2:

go

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.

Approach: Dynamic Programming

We can approach this problem using dynamic programming, similar to the classic Unique Paths problem, with an added condition to handle obstacles.

Steps:

1. Grid Setup: Create a DP table where each cell represents the number of unique ways to reach that cell from the top-left corner.
2. Base Case: If the starting cell (0, 0) contains an obstacle, return 0 because no path can begin from there.
3. Recurrence Relation: The number of unique paths to any cell (i, j) is the sum of the paths from the cell directly above it and the cell directly to the left of it. However, if a cell contains an obstacle, the number of paths to that cell is 0.
4. dp[i][j]=dp[i−1][j]+dp[i][j−1](if cell (i,j) is not an obstacle)dp[i][j] = dp[i-1][j] + dp[i][j-1] \quad \text{(if cell (i,j) is not an obstacle)}dp[i][j]=dp[i−1][j]+dp[i][j−1](if cell (i,j) is not an obstacle)
5. Final Answer: The value in the bottom-right corner (m-1, n-1) will give the total number of unique paths.

Go Implementation

go

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m := len(obstacleGrid)
    n := len(obstacleGrid[0])

    // If the starting point or the ending point is blocked, return 0
    if obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1 {
        return 0
    }

    // Create a 2D dp array
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    // Base case: the starting position
    dp[0][0] = 1

    // Fill the first column
    for i := 1; i < m; i++ {
        if obstacleGrid[i][0] == 0 {
            dp[i][0] = dp[i-1][0]
        }
    }

    // Fill the first row
    for j := 1; j < n; j++ {
        if obstacleGrid[0][j] == 0 {
            dp[0][j] = dp[0][j-1]
        }
    }

    // Fill the rest of the dp table
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if obstacleGrid[i][j] == 0 {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
    }

    // Return the value in the bottom-right corner
    return dp[m-1][n-1]
}

Example Walkthrough

For input:

go

obstacleGrid = [
    [0,0,0],
    [0,1,0],
    [0,0,0]
]

Step-by-step Explanation:

1. Initialize the DP table:

lua

dp = [[1, 0, 0],
      [0, 0, 0],
      [0, 0, 0]]

1. The first cell (0, 0) is the starting point, so it's initialized to 1.
2. Fill the first row:

lua

dp = [[1, 1, 1],
      [0, 0, 0],
      [0, 0, 0]]

1. The first row is free of obstacles, so each cell can be reached from the left.
2. Fill the first column:

lua

dp = [[1, 1, 1],
      [1, 0, 0],
      [1, 0, 0]]

1. The first column is free of obstacles, so each cell can be reached from above.
2. Fill the rest of the grid:

lua

dp = [[1, 1, 1],
      [1, 0, 1],
      [1, 1, 2]]

1. The grid is filled by checking the cells above and to the left of each cell. If a cell contains an obstacle, it's skipped.
2. Final Answer: The value in the bottom-right corner dp[2][2] = 2, meaning there are 2 unique paths.

Time and Space Complexity

MetricComplexityTime ComplexityO(m * n)Space ComplexityO(m * n)

• Time Complexity: The algorithm needs to fill a m x n DP table, resulting in a time complexity of O(m * n).
• Space Complexity: The space complexity is also O(m * n) because we are storing the results for all subproblems in a 2D array.

Optimizing Space Complexity

We can optimize the space complexity by using a 1D array to store the results of the current row. Since each cell only depends on the current row and the row directly above it, we can reduce the space complexity to O(n).

Here’s how to optimize the space:

go

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m := len(obstacleGrid)
    n := len(obstacleGrid[0])

    // If the starting point or the ending point is blocked, return 0
    if obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1 {
        return 0
    }

    // Create a 1D dp array for the current row
    dp := make([]int, n)
    dp[0] = 1

    // Fill the first row and first column
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if obstacleGrid[i][j] == 1 {
                dp[j] = 0
            } else if j > 0 {
                dp[j] += dp[j-1]
            }
        }
    }

    return dp[n-1]
}

In this optimized approach:

• We use a 1D array dp to store only the current row.
• The space complexity is reduced to O(n).

Edge Cases

• Empty grid: If the grid is empty, return 0.
• Blocked start or end: If either the start or end point is blocked, return 0.
• Small grids: A grid of size 1x1 will always have 1 unique path.
• Obstacles in various positions: Handle grids with obstacles at any location, ensuring the algorithm correctly accounts for blocked paths.

Key Takeaways

• Dynamic Programming: We used a DP approach similar to Unique Paths, but with the added complexity of handling obstacles.
• Space Optimization: By reducing the space complexity to O(n) using a 1D array, we can handle larger grids efficiently.
• Obstacles Handling: The grid's obstacles are taken into account by setting the corresponding DP cells to 0.