Skip to main content

🟨 Unique Paths (#62)

🔗 Problem Link​

📋 Problem Statement​

There is a robot on an m x n grid. The robot is 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.

Given m and n, return the number of possible unique paths.

💡 Examples​

Example 1​

Input: m = 3, n = 7
Output: 28

Example 2​

Input: m = 3, n = 2
Output: 3

🔑 Key Insights & Approach​

Core Observation: dp[i][j] = dp[i-1][j] + dp[i][j-1] (paths from top + paths from left).

Why 2D DP?

  • O(m * n) time, O(n) space optimized
  • Can optimize to 1D array
  • Classic grid DP

Pattern: "Grid Path Counting DP" pattern.

🐍 Solution: Python​

Approach: Space-Optimized DP​

Time Complexity: O(m * n) | Space Complexity: O(n)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n

        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j-1]

        return dp[n-1]

🔵 Solution: Golang​

Approach: 1D DP​

Time Complexity: O(m * n) | Space Complexity: O(n)

func uniquePaths(m int, n int) int {
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[j] += dp[j-1]
        }
    }

    return dp[n-1]
}

📚 References​