Unique Paths II - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Unique Paths II" Problem in Go

Difficulty: Medium | Tags: Array, Dynamic Programming, Matrix

Introduction

The "Unique Paths II" problem is a variation of the classic grid traversal problem, where a robot must navigate from the top-left corner to the bottom-right corner of a grid while avoiding obstacles. This problem tests your understanding of dynamic programming and matrix manipulation.

Problem Analysis

Given an m x n grid where obstacles are marked as 1 and empty spaces as 0, the robot can only move right or down. The goal is to count the number of unique paths from the start to the destination without passing through obstacles. For example, in a 3x3 grid with an obstacle at (1,1), there are exactly two valid paths.

Solution Approach

We use dynamic programming to solve this problem efficiently. The idea is to build a DP table where each cell (i, j) represents the number of ways to reach that cell. If the cell contains an obstacle, the value is 0. Otherwise, it's the sum of the ways to reach the cell from the top (i-1, j) and left (i, j-1). We initialize the first row and column carefully, considering obstacles.

Go Implementation


func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m := len(obstacleGrid)
    if m == 0 {
        return 0
    }
    n := len(obstacleGrid[0])
    if n == 0 {
        return 0
    }
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    // Initialize the first cell
    if obstacleGrid[0][0] == 0 {
        dp[0][0] = 1
    }
    // Initialize the first column
    for i := 1; i < m; i++ {
        if obstacleGrid[i][0] == 0 && dp[i-1][0] == 1 {
            dp[i][0] = 1
        }
    }
    // Initialize the first row
    for j := 1; j < n; j++ {
        if obstacleGrid[0][j] == 0 && dp[0][j-1] == 1 {
            dp[0][j] = 1
        }
    }
    // Fill 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 dp[m-1][n-1]
}

Complexity Analysis

The time complexity is O(m * n) because we traverse each cell of the grid exactly once. The space complexity is also O(m * n) due to the DP table. However, this can be optimized to O(n) by using a single array to store the current row's values.

Testing and Examples

Test case 1: Input [[0,0,0],[0,1,0],[0,0,0]] should return 2. Test case 2: Input [[0,1],[0,0]] should return 1. Edge cases include grids with obstacles at the start or end, which should return 0.

Best Practices and Tips

Always handle edge cases where the start or end cell is an obstacle. Optimize space by using a 1D DP array. Prefer dynamic programming for grid traversal problems with constraints.

Read more