62 - Unique Paths

Difficulty: Medium | Pattern: Dynamic Programming / Combinatorics | Company tags: Amazon, Google, Microsoft, Facebook

Problem Statement

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.

Example 1:

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

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: 3 paths: right→down→down, down→right→down, down→down→right

Constraints: 1 <= m, n <= 100

Approach 1: Dynamic Programming

Key insight: To reach cell (i, j), the robot must come from either (i-1, j) (from above) or (i, j-1) (from the left). So dp[i][j] = dp[i-1][j] + dp[i][j-1].

Base cases: Any cell in the first row or first column has exactly 1 path (can only go right or only go down).

Algorithm Flow

def uniquePaths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]

Space-optimized (single row):

def uniquePaths(m: int, n: int) -> int:
    row = [1] * n
    for _ in range(m - 1):
        for j in range(1, n):
            row[j] += row[j-1]
    return row[n-1]

Dry Run

m = 3, n = 3

Initial grid (all 1s in first row and column):

1  1  1
1  ?  ?
1  ?  ?

Fill in:

1  1  1
1  2  3
1  3  6

dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2 dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3 dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3 dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6

Result: 6 ✓

Approach 2: Combinatorics

The total path length is always (m-1) + (n-1) steps — (m-1) down moves and (n-1) right moves. The number of unique paths is the number of ways to choose which (m-1) of the total steps are "down" moves:

C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!)

from math import comb

def uniquePaths(m: int, n: int) -> int:
    return comb(m + n - 2, m - 1)

Example: m=3, n=7 → C(8, 2) = 28 ✓

Edge Cases

• m = 1 or n = 1: only 1 path (all right or all down)
• m = 1, n = 1: 1 path (already at destination)

Complexity

Approach	Time	Space
DP (2D grid)	O(m × n)	O(m × n)
DP (1D row)	O(m × n)	O(n)
Combinatorics	O(m + n)	O(1)