Unique Paths — Solution in Python, Java & C++
Unique Paths solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Ola and Razorpay.
Unique Paths is a medium coding problem on dynamic programming, math and combinatorics, asked in Ola and Razorpay interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Math, Combinatorics
- Asked at: Ola, Razorpay
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A robot starts at the top-left corner of an m x n grid and only moves right or down, aiming for the bottom-right corner.
Return the number of unique paths.
Example 1
Input: m = 3, n = 7
Output: 28
Example 2
Input: m = 3, n = 2
Output: 3
Explanation: Right→Down→Down, Down→Down→Right, Down→Right→Down.
Constraints
1 <= m, n <= 12
Hints for Unique Paths
Hint 1
paths(i,j) = paths(i-1,j) + paths(i,j-1); the edges have exactly one path.
Hint 2
It's also the binomial coefficient C(m+n-2, m-1).
How to solve Unique Paths
The robot reaches a cell only from directly above or directly to its left, so the number of paths to a cell is the sum of the paths to those two neighbours. The top row and left column each have exactly one path (straight along the edge), and filling the grid row by row gives the answer.
Approach
- Every cell in the first row and first column has exactly
1path. - For every other cell,
paths[i][j] = paths[i-1][j] + paths[i][j-1]. - Fill row by row so both predecessors are ready when needed.
- Only the previous row matters, so a single array of width
nsuffices —row[j] += row[j-1]updates in place.
Why it works
Each path arrives by a unique final move, from above or from the left, so the two sets of paths are disjoint and together exhaust every possibility — the sum is exact. The rolling-array trick works because when you reach row[j], it still holds the value from the row above (the paths[i-1][j] term) while row[j-1] has already been updated for the current row (the paths[i][j-1] term). Combinatorially the answer is C(m+n-2, m-1), choosing which of the moves go down.
Complexity
- Time —
O(m · n) - Space —
O(n)
Pitfalls
- Seed the first row and column to
1, not0. - With the rolling array, sweep
jleft to right — the in-place update depends on that order. - A single row or column has exactly one path, which the seeding handles.
- The closed-form binomial is exact but needs care to avoid overflow in the intermediate factorials.
Reference solution
Python
def uniquePaths(m: int, n: int) -> int:
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[n - 1]Java
public static int uniquePaths(int m, int n) {
int[] row = new int[n];
Arrays.fill(row, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) row[j] += row[j - 1];
}
return row[n - 1];
}C++
int uniquePaths(int m, int n) {
vector<int> row(n, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) row[j] += row[j - 1];
}
return row[n - 1];
}JavaScript
var uniquePaths = function(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];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming