Unique Paths
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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| 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
O(2^(m + n))O(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).
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);
}
}class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m == 1 or n == 1:
return 1
return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 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);
}
};function uniquePaths(m, n) {
if (m === 1 || n === 1) return 1;
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}2DP with one row
O(m · n)O(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].
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];
}
}class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[n - 1]class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> dp(n, 1);
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++) dp[j] += dp[j - 1];
return dp[n - 1];
}
};function uniquePaths(m, n) {
const dp = new Array(n).fill(1);
for (let i = 1; i < m; i++)
for (let j = 1; j < n; j++) dp[j] += dp[j - 1];
return dp[n - 1];
}3Combinatorics
O(min(m, n))O(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.
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;
}
}class Solution:
def uniquePaths(self, m: int, n: int) -> int:
N, k = m + n - 2, min(m, n) - 1
r = 1
for i in range(1, k + 1):
r = r * (N - k + i) // i
return rclass Solution {
public:
int uniquePaths(int m, int n) {
int N = m + n - 2, k = min(m, n) - 1;
long long r = 1;
for (int i = 1; i <= k; i++) r = r * (N - k + i) / i;
return (int) r;
}
};function uniquePaths(m, n) {
const N = m + n - 2, k = Math.min(m, n) - 1;
let r = 1;
for (let i = 1; i <= k; i++) r = r * (N - k + i) / i;
return 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).