Unique Paths

Difficulty: Medium
Topics: Math, Dynamic Programming, Combinatorics
Link: https://leetcode.com/problems/unique-paths/

Problem Description

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:


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

Example 2:


Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

1 <= m, n <= 100

Solution

1. Problem Deconstruction

Technical Restatement:
Given an m x n grid, compute the number of distinct paths from (0,0) to (m-1,n-1) using only right/down moves. Formally, find the cardinality of the set of all valid move sequences.

Beginner Explanation:
Imagine a grid where you start at the top-left corner. You can only move right or down. How many different ways can you reach the bottom-right corner without backtracking?

Mathematical Formulation:
The problem reduces to counting unique permutations of (m-1) downward and (n-1) rightward moves. The solution is the binomial coefficient:

C = \binom{(m-1)+(n-1)}{m-1} = \frac{(m+n-2)!}{(m-1)!(n-1)!}

Constraint Analysis:

1 <= m, n <= 100:
- Limitation: Brute-force recursion (O(2^(m+n))) is computationally infeasible.
- Edge Case: When m=1 or n=1, only 1 path exists (straight line).
Answer <= 2e9:
- Implication: Avoid floating-point inaccuracies in combinatorial calculations.

2. Intuition Scaffolding

Analogies:

City Navigation: Like taxis in Manhattan taking shortest routes via grid streets.
Game Strategy: Chess rook moving only south/east to reach a target square.
Math Puzzle: String permutations of “D” and “R” with fixed character counts.

Common Pitfalls:

Recursive DFS without memoization: Exponential time complexity.
Breadth-First Search (BFS): Queue size explodes for large grids.
Initializing DP grid incorrectly: First row/column should be all 1s.
Integer overflow in combinatorial calculations: Multiplying large factorials naively.
Assuming diagonal moves: Robot can’t move diagonally per problem constraints.

3. Approach Encyclopedia

1. Brute-Force Recursion:

def uniquePaths(m, n):
    if m == 1 or n == 1:
        return 1
    return uniquePaths(m-1, n) + uniquePaths(m, n-1)

Time: O(2^(m+n)) – Binary recursion tree depth.
Space: O(m+n) – Call stack depth.

2. Dynamic Programming (2D):

dp = [[1]*n for _ in range(m)]  
for i in 1 to m-1:
    for j in 1 to n-1:
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]

Time: O(mn) – Filling all grid cells.
Space: O(mn) – Storing full grid.

Visualization:

Initial Grid (3x3):  
1 1 1  
1 0 0  
1 0 0  

Final Grid:  
1 1 1  
1 2 3  
1 3 6  → Answer=6

3. Space-Optimized DP (1D):

dp = [1] * n  
for i in 1 to m-1:
    for j in 1 to n-1:
        dp[j] += dp[j-1]
return dp[-1]

Time: O(mn) – Same as 2D DP.
Space: O(n) – Single row storage.

4. Combinatorial Formula:

from math import comb  
return comb(m+n-2, m-1)

Time: O(min(m,n)) – Multiplicative loop iterations.
Space: O(1) – Constant variables.

Multiplicative Implementation:

a = m + n - 2  
b = min(m-1, n-1)  
result = 1  
for i in 1..b:  
    result = result * (a - b + i) // i  
return result

4. Code Deep Dive

Optimal Solution (Combinatorial):

def uniquePaths(m: int, n: int) -> int:
    a = m + n - 2
    b = min(m-1, n-1)
    result = 1
    for i in range(1, b+1):
        result = result * (a - b + i) // i
    return result

Line-by-Line:

a = m + n - 2 → Total moves needed.
b = min(...) → Optimize calculation by choosing smaller factorial.
result initialized to 1 → Identity for multiplication.
Loop computes numerator incrementally while dividing by i → Prevents overflow.

Edge Case Handling:

m=1 → b=0, loop skipped → Returns 1.
Division at each step → Ensures integer arithmetic.

5. Complexity War Room

Hardware Considerations:

Combinatorial approach uses 32-bit integers safely (answer <=2e9).
DP approaches fit in L1 cache for m,n=100 (grid size=10,000 → ~40KB).

Approach Comparison:

Method	Time	Space	Readability	Viability
Brute Force	O(2^N)	O(N)	5/10	❌
2D DP	O(mn)	O(mn)	9/10	✅
1D DP	O(mn)	O(n)	7/10	✅
Combinatorial	O(k)	O(1)	6/10	✅★

6. Pro Mode Extras

Variants:

Obstacles in Grid (LC 63): Use DP with obstacle checks.
Multiple Transactions (LC 123): Extend DP to track state.

Interview Tips:

First Mention: “The optimal solution uses combinatorics with O(1) space.”
Edge Case: Always check for grids with zero width/height (but constraints prevent this here).
Tradeoffs: “DP is more intuitive but combinatorial is optimal for large grids.”

#62 - Unique Paths