#62 Unique Paths

frequently reported atAmazon Bloomberg Meta Google Goldman Sachs

the problem

In plain words

A robot starts at the top-left of an m × n grid and moves only right or down. How many different paths reach the bottom-right corner?

in m = 3, n = 7

out 28

in m = 3, n = 2

out 3

R→D→D, D→D→R, D→R→D.

1 ≤ m, n ≤ 100
The answer is ≤ 2·10⁹

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternGrid DP Math shortcut (closed form)

Every path into a cell arrives from above or from the left, so paths(r, c) = paths(r−1, c) + paths(r, c−1). Top row and left column have exactly one path.

solutions

From brute force to optimal

paths(r, c) = paths(r−1, c) + paths(r, c−1).

Edge (r = 0 or c = 0) → 1.
Sum the two sub-calls.

timeO(2^(m+n))

Two branches per step, path length m + n − 2.

spaceO(m + n)

Recursion depth.

javajava.util.*

1class Solution {2    public int uniquePaths(int m, int n) {3        return paths(m - 1, n - 1);4    }5 6    /** Paths from (0,0) to (r,c) moving only right/down. */7    private int paths(int r, int c) {8        if (r == 0 || c == 0) return 1; // top row / left column: one straight path9        return paths(r - 1, c) + paths(r, c - 1); // arrived from above or from the left10    }11}

Cache paths(r, c) in an m × n array (0 = unknown; real answers ≥ 1).

Check memo, compute, store.

timeO(m·n)

Each cell once.

spaceO(m·n)

Memo + stack.

javajava.util.*

1class Solution {2    public int uniquePaths(int m, int n) {3        return paths(m - 1, n - 1, new int[m][n]);4    }5 6    private int paths(int r, int c, int[][] memo) {7        if (r == 0 || c == 0) return 1;8        if (memo[r][c] != 0) return memo[r][c];9        return memo[r][c] = paths(r - 1, c, memo) + paths(r, c - 1, memo);10    }11}

Fill row by row, left to right.

Edges = 1.
dp[r][c] = dp[r−1][c] + dp[r][c−1].

timeO(m·n)

One O(1) step per cell.

spaceO(m·n)

The table.

javajava.util.*

1class Solution {2    public int uniquePaths(int m, int n) {3        int[][] dp = new int[m][n]; // dp[r][c] = paths that reach (r, c)4        for (int r = 0; r < m; r++) {5            for (int c = 0; c < n; c++) {6                if (r == 0 || c == 0) dp[r][c] = 1; // edges: only one way in7                else dp[r][c] = dp[r - 1][c] + dp[r][c - 1]; // from above + from left8            }9        }10        return dp[m - 1][n - 1];11    }12}

sim

Raise the landscape

loading simulation…

javajava.util.*

1class Solution {2    public int uniquePaths(int m, int n) {3        int[][] dp = new int[m][n]; // dp[r][c] = paths that reach (r, c)4        for (int r = 0; r < m; r++) {5            for (int c = 0; c < n; c++) {6                if (r == 0 || c == 0) dp[r][c] = 1; // edges: only one way in7                else dp[r][c] = dp[r - 1][c] + dp[r][c - 1]; // from above + from left8            }9        }10        return dp[m - 1][n - 1];11    }12}

dp[c] += dp[c−1]: old dp[c] is "from above", dp[c−1] is "from the left".

dp = all 1s (top row).
For each next row: for c = 1..n−1: dp[c] += dp[c−1].

timeO(m·n)

Same updates.

spaceO(n)

One row.

javajava.util.*

1class Solution {2    public int uniquePaths(int m, int n) {3        int[] dp = new int[n]; // dp[c] = paths into column c of the current row4        Arrays.fill(dp, 1); // the top row5        for (int r = 1; r < m; r++) {6            for (int c = 1; c < n; c++) {7                dp[c] += dp[c - 1]; // old dp[c] = from above, dp[c-1] = from left (already this row)8            }9        }10        return dp[n - 1];11    }12}

sim

One row does the whole grid

loading simulation…

javajava.util.*

1class Solution {2    public int uniquePaths(int m, int n) {3        int[] dp = new int[n]; // dp[c] = paths into column c of the current row4        Arrays.fill(dp, 1); // the top row5        for (int r = 1; r < m; r++) {6            for (int c = 1; c < n; c++) {7                dp[c] += dp[c - 1]; // old dp[c] = from above, dp[c-1] = from left (already this row)8            }9        }10        return dp[n - 1];11    }12}

A path is m−1 downs and n−1 rights in some order: C(m+n−2, m−1).

Multiply and divide step by step in a long so every intermediate value is an exact integer.

timeO(m)

m − 1 multiply/divide steps (pick the smaller of m, n for O(min(m, n))).

spaceO(1)

One long.

javajava.util.*

1class Solution {2    /** Any path is (m-1) downs and (n-1) rights in some order: choose where the downs go. */3    public int uniquePaths(int m, int n) {4        long result = 1;5        int downs = m - 1, total = m + n - 2;6        for (int k = 1; k <= downs; k++) {7            result = result * (total - downs + k) / k; // stays an exact integer at every step8        }9        return (int) result;10    }11}

in the room

How to say it in the interview

talk track

Give the DP first (it generalises to obstacles), then mention the closed form as a bonus.

traps

Computing factorials directly overflows even a long (21! already does). Multiply-then-divide incrementally instead.

what they ask next

Follow-ups

Obstacles (LC 63)?

Same DP; an obstacle cell is 0. The combinatorics shortcut no longer works. See Unique Paths II below.

Min cost path?

That's Minimum Path Sum (LC 64): min instead of +.

before you submit

Edge cases to test

1 × 1 → 1 (already at the goal).
1 × n or m × 1 → 1 straight path.
17 × 18 → 1,166,803,110: fine for the DP, but the factorial formula needs 33!, which overflows a long.

practise next