Medium#628 min readCombinatoricsDynamic ProgrammingLeetCode

Unique Paths

Binomial coefficient

dp[i][j] = dp[i-1][j] + dp[i][j-1]. Grid DP starting point.

Published Apr 16, 2026

Problem

A robot starts at the top-left corner of an m × n grid. It can only move right or down one cell at a time and wants to reach the bottom-right corner. How many distinct paths are there?

Input

m = 3, n = 7

Output

Explanation

The robot must take exactly 2 down moves and 6 right moves in some order — 8 moves total. The number of distinct orderings is C(8, 2) = 28.

Input

m = 3, n = 2

Output

Explanation

Three orderings of DDR, DRD, RDD.

Intuition

Every path from (0, 0) to (m-1, n-1) is a sequence of m - 1 downs and n - 1 rights — exactly m + n - 2 moves. The robot's entire freedom is the order of those moves.

Counting orderings of a multiset is the textbook setup for a binomial coefficient:

paths(m, n) = C(m + n - 2, m - 1)

Three solutions at increasing levels of polish:

Naïve recursion. Split on the first move (down or right). Exponential — demonstrates the shape.
2D DP. Fill a grid where dp[i][j] counts paths to cell (i, j). Polynomial O(mn).
Direct binomial. Compute C(m+n-2, m-1) with an iterative product. Linear in min(m, n), constant space.

Approach

Recursive Brute

TimeO(2^(m+n))

SpaceO(m+n)

Start at (0, 0). Either step down or step right. Base case: at the goal, that's one path.

Exponential because the recursion tree has roughly 2^(m+n) leaves — most of them revisiting the same subgrids. Only ships for tiny grids; it exists to make the recurrence f(i, j) = f(i-1, j) + f(i, j-1) explicit.

impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        fn paths(i: i32, j: i32, m: i32, n: i32) -> i32 {
            if i == m - 1 && j == n - 1 {
                return 1;
            }
            let mut total = 0;
            if i + 1 < m {
                total += paths(i + 1, j, m, n);
            }
            if j + 1 < n {
                total += paths(i, j + 1, m, n);
            }
            total
        }
        paths(0, 0, m, n)
    }
}

Rust · runnable

function uniquePaths(m: number, n: number): number {
  const paths = (i: number, j: number): number => {
    if (i === m - 1 && j === n - 1) return 1;
    let total = 0;
    if (i + 1 < m) total += paths(i + 1, j);
    if (j + 1 < n) total += paths(i, j + 1);
    return total;
  };
  return paths(0, 0);
}

TypeScript · runnable

2D DP

TimeO(m · n)

SpaceO(m · n)

Fill a table left-to-right, top-to-bottom. Each cell's value is the sum of the cell above and the cell to the left. The first row and first column are all 1 — only one way to walk a straight line.

Every subproblem is computed exactly once. Space drops to O(n) with a rolling row; we keep the 2D form for clarity.

impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        let m = m as usize;
        let n = n as usize;
        let mut dp = vec![vec![1i64; n]; m];
        for i in 1..m {
            for j in 1..n {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        dp[m - 1][n - 1] as i32
    }
}

Rust · runnable

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

TypeScript · runnable

Binomial Coefficient

TimeO(min(m, n))

SpaceO(1)

Recommended

Directly compute C(m+n-2, m-1). The iterative product keeps the running value as an integer at every step by multiplying by the next numerator term before dividing by the next denominator term — denominators always divide cleanly when applied in order.

Pick the smaller of m-1 and n-1 as k to halve the loop count: C(n, k) == C(n, n-k).

impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        let total = (m + n - 2) as u64;
        let k = std::cmp::min(m - 1, n - 1) as u64;
        let mut result: u64 = 1;
        for i in 0..k {
            result = result * (total - i) / (i + 1);
        }
        result as i32
    }
}

Rust · runnable

function uniquePaths(m: number, n: number): number {
  const total = m + n - 2;
  const k = Math.min(m - 1, n - 1);
  let result = 1;
  for (let i = 0; i < k; i++) {
    result = (result * (total - i)) / (i + 1);
  }
  return result;
}

TypeScript · runnable

The division is exact at every step because result at iteration i equals C(total, i+1) * (something integral) — concretely result_{i+1} = result_i * (total - i) / (i + 1) always lands on a valid binomial-coefficient partial product. For LeetCode's constraints (m, n ≤ 100), total ≤ 198 and the final value fits comfortably in i32.

Trace

Binomial product for m = 3, n = 7: C(8, 2).

i	term multiplied	term divided	running result
0	8	1	8
1	7	2	28

Final answer 28. ✓

2D DP for m = 3, n = 2:

row i	col 0	col 1
0	1	1
1	1	2
2	1	3

Bottom-right is 3. ✓

Edge cases

m = 1 or n = 1 — single row or column; the only path is straight. Binomial formula gives C(total, 0) = 1.
Square grid — m = n has C(2m-2, m-1) paths; central binomial coefficient.
Maximum LeetCode grid 100 × 100 — C(198, 99) exceeds i32::MAX, but the stated constraint guarantees the answer itself fits — m · n ≤ 2 · 10^9 in the intermediate product. The binomial form naturally stays in u64; the DP form needs i64 internally.

💡

Tip

C(n, k) via iterative product is the standard way to avoid factorial overflow when the final coefficient fits but intermediate factorials don't. Pair it with modular inverse when you need modular answers (see #1569, #2514).

Takeaway

When you count orderings of a fixed multiset of moves, the answer is a binomial coefficient. DP works and teaches you the recurrence; the closed form is faster and is what you reach for in production code paths (search ranking, path enumeration, combinatorial sampling).

The recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1] is Pascal's triangle in grid form. Once you spot the symmetry, the jump from O(mn) DP to O(min(m, n)) binomial is immediate.