LeetCode 62: Unique Paths Solution in Python Explained

Problem Statement

LeetCode 62, Unique Paths, is a medium-level problem where you’re given two integers m and n, representing an (m \times n) grid. Your task is to find the number of unique paths from the top-left corner (1,1) to the bottom-right corner (m,n), moving only right or down at each step. Return the total number of possible paths as an integer.

Constraints

1 <= m, n <= 100: Grid dimensions are between 1 and 100.
The answer will fit within a 32-bit signed integer.

Example

Input: m = 3, n = 2
Output: 3
Explanation: 3x2 grid paths:
1. Right -> Down -> Down
2. Down -> Right -> Down
3. Down -> Down -> Right

Input: m = 3, n = 7
Output: 28
Explanation: 3x7 grid has 28 unique paths.

Input: m = 2, n = 2
Output: 2
Explanation: 2x2 grid: Right->Down or Down->Right.

Understanding the Problem

How do you solve LeetCode 62: Unique Paths in Python? For m = 3, n = 2, count the unique paths from (1,1) to (3,2) in a 3x2 grid, moving only right or down—here, there are 3 paths. Each path requires exactly (m-1) down moves and (n-1) right moves, totaling (m+n-2) steps. We’ll explore two approaches: a Dynamic Programming Solution (optimal and primary) and an Alternative with Combinatorial Math (elegant and fast). The DP method runs in O(m * n) time with O(m * n) space, while the math solution is O(min(m,n)) with O(1) space.

Solution 1: Dynamic Programming Approach (Primary)

Explanation

Use a 2D DP table where dp[i][j] represents the number of unique paths to reach position (i,j) from (0,0). Since you can only move right or down, dp[i][j] = dp[i-1][j] + dp[i][j-1]. Initialize the first row and column to 1 (only one way to reach each), then fill the table.

Here’s a flow for (m = 3, n = 2):

DP table:
[1,1]    [1,1]
[1,2] -> [1,2]
[1,3]    [1,3]
Result: dp[2][1] = 3

Initialize DP Table.

Create \(m \times n\) table, set first row and column to 1.

Fill Table.

For each cell, sum paths from above and left.

Return Result.

Value at dp[m-1][n-1].

Step-by-Step Example

Example 1: m = 3, n = 2

We need 3.

Goal: Count unique paths in 3x2 grid.
Result for Reference: 3.
Start: m = 3, n = 2, dp = [[0,0],[0,0],[0,0]].
Step 1: Initialize first row and column.

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

Step 2: Fill table.

dp[1][1] = dp[1][0] + dp[0][1] = 1 + 1 = 2.
dp[2][1] = dp[2][0] + dp[1][1] = 1 + 2 = 3.
dp = [[1,1],[1,2],[1,3]].

Finish: Return dp[2][1] = 3.

Example 2: m = 2, n = 2

We need 2.

Start: dp = [[0,0],[0,0]].
Step 1: Initialize.

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

Step 2: Fill.

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

Finish: Return dp[1][1] = 2.

How the Code Works (Dynamic Programming)

Here’s the Python code with line-by-line explanation:

def uniquePaths(m: int, n: int) -> int:
    # Line 1: Initialize DP table
    dp = [[1] * n for _ in range(m)]

    # Line 2: Fill table (first row and column already 1)
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    # Line 3: Return number of unique paths
    return dp[m-1][n-1]

Alternative: Combinatorial Math Approach

Explanation

Recognize that each path requires exactly (m-1) down moves and (n-1) right moves, totaling (m+n-2) steps. The number of unique paths is the number of ways to choose (m-1) down moves (or (n-1) right moves) from (m+n-2) total moves, which is the binomial coefficient (C(m+n-2, m-1)). Compute this efficiently to avoid overflow.

Formulate Combination.

\(C(m+n-2, m-1) = \frac{(m+n-2)!}{(m-1)! * (n-1)!}\).

Optimize Calculation.

Use smaller of \(m-1\) or \(n-1\) to reduce iterations, compute iteratively.

Return Result.

Step-by-Step Example (Alternative)

For (m = 3, n = 2):

Start: Total moves = \(m+n-2 = 3+2-2 = 3\), down = \(m-1 = 2\), right = \(n-1 = 1\).
Step 1: \(C(3, 2) = C(3, 1) = \frac{3!}{1! * 2!} = \frac{6}{2} = 3\).
Step 2: Compute iteratively.

Numerator = 3, denominator = 1, result = 3.

Finish: Return 3.

For (m = 3, n = 7):

Start: Total = 8, down = 2, right = 6, \(C(8, 2) = \frac{8*7}{2*1} = 28\).
Finish: Return 28.

How the Code Works (Combinatorial Math)

def uniquePathsMath(m: int, n: int) -> int:
    # Line 1: Total moves and choose smaller
    total = m + n - 2
    k = min(m - 1, n - 1)

    # Line 2: Compute combination C(total, k)
    result = 1
    for i in range(k):
        result *= (total - i)
        result //= (i + 1)

    # Line 3: Return number of unique paths
    return result

Complexity

Dynamic Programming:

Time: O(m * n) – Fill \(m \times n\) table.
Space: O(m * n) – Store DP table.

Combinatorial Math:

Time: O(min(m,n)) – Compute combination with smaller value.
Space: O(1) – Only one variable.

Efficiency Notes

Combinatorial Math is O(min(m,n)) time and O(1) space, more efficient than DP’s O(m * n) time and space, making it ideal for LeetCode 62 when memory is a concern. DP is more versatile and intuitive for grid-based problems.

Key Insights

Tips to master LeetCode 62:

Move Count: \(m-1\) down, \(n-1\) right, total \(m+n-2\).
DP Simplicity: Sum paths from above and left.
Math Efficiency: Use combinations for direct calculation.

Additional Example

For (m = 4, n = 1):

Goal: 1.
DP: dp[3][0] = 1 (only down).
Math: \(C(3, 3) = 1\).
Result: 1.

Edge Cases

\(m = 1, n = 1\): 1 (no moves).
\(m = 1, n = k\): 1 (only right).
\(m = 100, n = 100\): Large value, fits 32-bit int.

Final Thoughts

The Dynamic Programming solution is a solid choice for LeetCode 62 in Python—clear, reliable, and grid-friendly, though the Combinatorial Math approach shines for efficiency. For a related challenge, try LeetCode 61: Rotate List to switch to linked lists! Ready to pathfind? Solve LeetCode 62 on LeetCode now and test it with (m=3, n=2) or (m=3, n=7) to master unique paths. Dive in and navigate the grid!