Solving the LeetCode "Unique Paths" Problem in Go

Difficulty: Medium | Tags: Math, Dynamic Programming, Combinatorics

Introduction

The "Unique Paths" problem involves calculating the number of distinct paths a robot can take from the top-left corner to the bottom-right corner of an m x n grid, moving only right or down.

Problem Analysis

The robot starts at (0, 0) and must reach (m-1, n-1). At each step, it can move either right or down. The challenge is to count all possible unique paths without retracing steps. For example, a 3x7 grid yields 28 unique paths, while a 3x2 grid has 3 paths.

Solution Approach

We use dynamic programming to solve this problem efficiently. Create a 2D array dp where dp[i][j] represents the number of unique paths to reach cell (i, j). Initialize the first row and column to 1 since there's only one way to reach any cell in the first row or column. For other cells, dp[i][j] = dp[i-1][j] + dp[i][j-1].

Go Implementation

func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][0] = 1
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}

Complexity Analysis

Time complexity: O(m * n) because we fill an m x n table. Space complexity: O(m * n) due to the DP table. Optimizations can reduce space to O(n) by reusing a single row.

Testing and Examples

Test cases include:
1. m = 3, n = 7 → 28
2. m = 3, n = 2 → 3
3. m = 1, n = 1 → 1 (edge case)
4. m = 100, n = 100 → large output (stress test)

Best Practices and Tips

Key takeaways:
- Prefer dynamic programming for grid traversal problems.
- Initialize boundary conditions first.
- Optimize space by reusing rows or columns.
- Test edge cases like 1x1 grid or large grids.