62. Unique Paths (Medium)

Problem

A robot is on an m × n grid, at the top-left. It can only move right or down. Return the number of unique paths to the bottom-right.

Example

• m = 3, n = 7 → 28
• m = 3, n = 2 → 3

LeetCode 62 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Recursive

f(r, c) = f(r, 1, c) + f(r, c, 1) with f(0, c) = f(r, 0) = 1.

Python

def unique_paths(m, n):
    def f(r, c):                          # L1: define recursive helper
        if r == 0 or c == 0:              # L2: O(1) base case (edge row/col)
            return 1
        return f(r - 1, c) + f(r, c - 1) # L3: two recursive calls
    return f(m - 1, n - 1)

TypeScript

function uniquePaths(m: number, n: number): number {
    function f(r: number, c: number): number {   // L1: define recursive helper
        if (r === 0 || c === 0) return 1;        // L2: O(1) base case (edge row/col)
        return f(r - 1, c) + f(r, c - 1);       // L3: two recursive calls
    }
    return f(m - 1, n - 1);
}

Go

func uniquePaths(m int, n int) int {
    var f func(r, c int) int              // L1: define recursive helper
    f = func(r, c int) int {
        if r == 0 || c == 0 { return 1 } // L2: O(1) base case (edge row/col)
        return f(r-1, c) + f(r, c-1)     // L3: two recursive calls
    }
    return f(m-1, n-1)
}

Swift

final class Solution {
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        func solve(_ row: Int, _ col: Int) -> Int {
            if row == m - 1 || col == n - 1 { return 1 }
            return solve(row + 1, col) + solve(row, col + 1)
        }
        return solve(0, 0)
    }
}

Where the time goes, line by line

Variables: m = number of grid rows, n = number of grid columns.

Line	Per-call cost	Times executed	Contribution
L2 (base case)	$O(1)$	once per leaf call	$O(1)$ each
L3 (two recursive calls)	$O(1)$ work + 2 calls	$O(2^{m+n})$ call tree	$O(2^{m+n})$ ← dominates

Without caching, the same (r, c) is recomputed at every node of a binary tree of depth m + n. The exponential blowup is identical to naive Fibonacci.

Complexity

• Time: $O(2^{m+n})$, driven by L3’s double branching without memoization.
• Space: $O(m + n)$ recursion depth.

Approach 2: 2-D bottom-up DP

dp[r][c] = paths to (r, c).

Python

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]   # L1: O(m*n) init, all 1s (edges are base cases)
    for r in range(1, m):              # L2: outer loop O(m)
        for c in range(1, n):          # L3: inner loop O(n)
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]  # L4: O(1) recurrence
    return dp[m - 1][n - 1]            # L5: O(1) read answer

TypeScript

function uniquePaths(m: number, n: number): number {
    const dp: number[][] = Array.from({ length: m }, () => new Array(n).fill(1));  // L1: O(m*n) init
    for (let r = 1; r < m; r++) {                     // L2: outer loop O(m)
        for (let c = 1; c < n; c++) {                 // L3: inner loop O(n)
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1];  // L4: O(1) recurrence
        }
    }
    return dp[m - 1][n - 1];                          // L5: O(1) read answer
}

Go

func uniquePaths(m int, n int) int {
    dp := make([][]int, m)                   // L1: O(m*n) init, all 1s
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] { dp[i][j] = 1 }
    }
    for r := 1; r < m; r++ {                // L2: outer loop O(m)
        for c := 1; c < n; c++ {            // L3: inner loop O(n)
            dp[r][c] = dp[r-1][c] + dp[r][c-1]  // L4: O(1) recurrence
        }
    }
    return dp[m-1][n-1]                     // L5: O(1) read answer
}

Where the time goes, line by line

Variables: m = number of grid rows, n = number of grid columns.

Line	Per-call cost	Times executed	Contribution
L1 (table init)	$O(1)$ per cell	m · n	$O(m · n)$
L2+L3 (double loop)	$O(1)$ body	(m-1) · (n-1)	$O(m · n)$ ← dominates
L4 (recurrence fill)	$O(1)$	(m-1) · (n-1)	$O(m · n)$
L5 (answer read)	$O(1)$	1	$O(1)$

Every cell is visited once; each fill is a single addition. The double loop is the only work.

Complexity

• Time: $O(m · n)$, driven by L2+L3+L4 (the full grid traversal).
• Space: $O(m · n)$ for the DP table.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        var dp = Array(repeating: Array(repeating: 1, count: n), count: m)
        if m > 1 && n > 1 {
            for row in stride(from: m - 2, through: 0, by: -1) {
                for col in stride(from: n - 2, through: 0, by: -1) { dp[row][col] = dp[row + 1][col] + dp[row][col + 1] }
            }
        }
        return dp[0][0]
    }
}

Approach 3: 1-D rolling array (optimal space)

dp[c] holds the current row; update in place.

Python

def unique_paths(m, n):
    dp = [1] * n          # L1: O(n) init (first row, all paths = 1)
    for _ in range(1, m): # L2: outer loop O(m)
        for c in range(1, n):          # L3: inner loop O(n)
            dp[c] += dp[c - 1]         # L4: O(1) in-place update
    return dp[n - 1]      # L5: O(1) read answer

TypeScript

function uniquePaths(m: number, n: number): number {
    const dp: number[] = new Array(n).fill(1);  // L1: O(n) init (first row, all paths = 1)
    for (let r = 1; r < m; r++) {               // L2: outer loop O(m)
        for (let c = 1; c < n; c++) {           // L3: inner loop O(n)
            dp[c] += dp[c - 1];                 // L4: O(1) in-place update
        }
    }
    return dp[n - 1];                           // L5: O(1) read answer
}

Go

func uniquePaths(m int, n int) int {
    dp := make([]int, n)             // L1: O(n) init (first row, all paths = 1)
    for i := range dp { dp[i] = 1 }
    for r := 1; r < m; r++ {        // L2: outer loop O(m)
        for c := 1; c < n; c++ {    // L3: inner loop O(n)
            dp[c] += dp[c-1]        // L4: O(1) in-place update
        }
    }
    return dp[n-1]                  // L5: O(1) read answer
}

Where the time goes, line by line

Variables: m = number of grid rows, n = number of grid columns.

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$ per element	n	$O(n)$
L2+L3 (double loop)	$O(1)$ body	(m-1) · (n-1)	$O(m · n)$ ← dominates
L4 (rolling update)	$O(1)$	(m-1) · (n-1)	$O(m · n)$

Same time complexity as 2-D DP but the space drops from $O(m · n)$ to $O(n)$ by reusing one array. dp[c] before the update is dp[r-1][c] (from the previous row); dp[c-1] just updated is dp[r][c-1] from the current row. The rolling update is sound because we traverse left to right.

Complexity

• Time: $O(m · n)$, driven by L2+L3+L4.
• Space: $O(n)$ for the single rolling row.

Closed-form (math variant)

The answer is C(m + n - 2, m - 1), choose which m - 1 of the m + n - 2 total moves are “down.” $O(min(m, n)$) using iterative factorial.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        var row = Array(repeating: 1, count: n)
        if m > 1 && n > 1 {
            for _ in stride(from: m - 2, through: 0, by: -1) {
                for col in stride(from: n - 2, through: 0, by: -1) { row[col] += row[col + 1] }
            }
        }
        return row[0]
    }
}

Summary

Approach	Time	Space
Recursive	$O(2^{m+n})$	$O(m + n)$
2-D DP	$O(m · n)$	$O(m · n)$
1-D rolling DP	$O(m · n)$	$O(n)$
Closed-form	$O(min(m, n)$)	$O(1)$

The 1-D rolling array is the standard interview answer. The closed-form is a neat math flex when permitted.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_062.py and run.
# Uses the canonical implementation (Approach 3: 1-D rolling DP).

def unique_paths(m, n):
    dp = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            dp[c] += dp[c - 1]
    return dp[n - 1]

def _run_tests():
    # problem statement examples
    assert unique_paths(3, 7) == 28
    assert unique_paths(3, 2) == 3
    # edge: 1x1 grid
    assert unique_paths(1, 1) == 1
    # edge: single row (only one path: all right)
    assert unique_paths(1, 5) == 1
    # edge: single column (only one path: all down)
    assert unique_paths(5, 1) == 1
    # larger case
    assert unique_paths(3, 3) == 6
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function uniquePaths(m: number, n: number): number {
    const dp: number[] = new Array(n).fill(1);
    for (let r = 1; r < m; r++)
        for (let c = 1; c < n; c++)
            dp[c] += dp[c - 1];
    return dp[n - 1];
}

console.assert(uniquePaths(3, 7) === 28);
console.assert(uniquePaths(3, 2) === 3);
console.assert(uniquePaths(1, 1) === 1);
console.assert(uniquePaths(1, 5) === 1);
console.assert(uniquePaths(5, 1) === 1);
console.assert(uniquePaths(3, 3) === 6);
console.log("all tests pass");

Go

package main

import "fmt"

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

func main() {
    if uniquePaths(3, 7) != 28 { panic("fail") }
    if uniquePaths(3, 2) != 3 { panic("fail") }
    if uniquePaths(1, 1) != 1 { panic("fail") }
    if uniquePaths(1, 5) != 1 { panic("fail") }
    if uniquePaths(5, 1) != 1 { panic("fail") }
    if uniquePaths(3, 3) != 6 { panic("fail") }
    fmt.Println("all tests pass")
}

Related data structures

• Arrays, DP grid; rolling array

Related concepts

• Grid DP, row-column DP tactics for paths, matrix states, and local moves with directional dependencies.
• State Compression, dP memory tactics for keeping only the previous states needed for the next transition.
• Tabulation, bottom-up DP tactics for filling states in dependency order without recursion.