Unique Paths

Medium Dynamic Programming 2D DP Original on LeetCode

Unique Paths is a medium dynamic programming problem solved with the 2d dp pattern. The best approach, combinatorics, runs in O(min(m, n)) time and O(1) space. Below are 3 approaches in Java, from recursion up.

Problem

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

Examples

Example 1

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

Example 2

Input: m = 3, n = 2
Output: 3

Constraints

1 <= m, n <= 100; the answer fits in an int.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Recursion	`O(2^(m + n))`	`O(m + n)`
DP with one row	`O(m · n)`	`O(n)`
Combinatorics	`O(min(m, n))`	`O(1)`

1Recursion

TimeO(2^(m + n))

SpaceO(m + n)

Every path into a cell comes from above or from the left.

paths(0, ) = paths(, 0) = 1.
paths(i, j) = paths(i - 1, j) + paths(i, j - 1).

Java

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) return 1;
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
}

2DP with one row

TimeO(m · n)

SpaceO(n)

Row by row, dp[j] += dp[j - 1]: the old dp[j] is the count from above and dp[j - 1] is the count from the left.

dp = all 1s (first row).
For each next row: for j >= 1, dp[j] += dp[j - 1].

Java

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++) dp[j] += dp[j - 1];
        return dp[n - 1];
    }
}

3Combinatorics

TimeO(min(m, n))

SpaceO(1)

Every path is a sequence of m - 1 downs and n - 1 rights. The count is C(m + n - 2, m - 1), computed with a running product that stays an integer at each step.

r = 1; for i in 1..k: r = r * (N - k + i) / i.

Java

class Solution {
    public int uniquePaths(int m, int n) {
        int N = m + n - 2, k = Math.min(m, n) - 1;
        long r = 1;
        for (int i = 1; i <= k; i++) r = r * (N - k + i) / i;
        return (int) r;
    }
}

Edge cases to test

m = 1 or n = 1 (one path)

Hints

Hint 1

paths(i, j) = paths(i - 1, j) + paths(i, j - 1). Or count arrangements of m - 1 downs and n - 1 rights.

FAQ

What is the best time complexity for Unique Paths?

Combinatorics runs in O(min(m, n)) time and O(1) extra space.

Which pattern does Unique Paths use?

It is a dynamic programming problem that uses the 2d dp pattern. Other problems with the same pattern: Minimum Path Sum, Unique Paths II.

Is there a brute force solution for Unique Paths?

Yes. Recursion takes O(2^(m + n)) time and O(m + n) space. Every path into a cell comes from above or from the left.

Which edge cases should I test for Unique Paths?

m = 1 or n = 1 (one path).