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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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.

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 code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
RecursionO(2^(m + n))O(m + n)
DP with one rowO(m · n)O(n)
CombinatoricsO(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.

  1. paths(0, ) = paths(, 0) = 1.
  2. paths(i, j) = paths(i - 1, j) + paths(i, j - 1).
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.

  1. dp = all 1s (first row).
  2. For each next row: for j >= 1, dp[j] += dp[j - 1].
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.

  1. r = 1; for i in 1..k: r = r * (N - k + i) / i.
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, Dungeon Game.

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).