Approach Summary
dp[i][j] = paths from (0,0) to (i,j) = dp[i-1][j] + dp[i][j-1]. Row/column of 1s are base cases. Space-optimized to O(n).
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: 2D Dynamic Programming Grid | O(m * n) | O(m * n) | Tabulate unique paths in an m x n matrix using dp[i][j] = dp[i-1][j] + dp[i][j-1]. |
| 2 Approach 2: 1D Rolling Row Space Optimization (Optimal) | O(m * n) | O(n) | Reuse a 1D array of length n where dp[j] accumulates paths from top (previous dp[j]) and left (dp[j-1]). |
Step 1: Baseline
Approach 1: 2D Dynamic Programming Grid
Time: O(m * n)
Space: O(m * n)
Allocate a 2D matrix dp of dimension m x n. The first row dp[0][j] and first column dp[i][0] are all set to 1. For every cell (i, j) with i > 0 and j > 0, sum the paths coming from above dp[i-1][j] and from the left dp[i][j-1]. Return dp[m-1][n-1].
Approach 1: 2D Dynamic Programming Grid Implementation
Approach 1: 2D Dynamic Programming Grid
class Solution {
public int uniquePaths(int m, int n) {
int dp[][] = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[m - 1][n - 1];
}
}class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[m - 1][n - 1];
}
};class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]function uniquePaths(m, n) {
const dp = Array.from({ length: m }, () => new Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
} Step 2: Most Optimized
Approach 2: 1D Rolling Row Space Optimization (Optimal)
Time: O(m * n)
Space: O(n)
Since calculating row i only uses entries from row i - 1 and the newly computed cells of row i, we can compress the 2D grid into a single 1D array of length n initialized to 1. On each row pass from 1 to m - 1, update dp[j] += dp[j - 1].
Approach 2: 1D Rolling Row Space Optimization (Optimal) Implementation
Approach 2: 1D Rolling Row Space Optimization (Optimal)
class Solution {
public int uniquePaths(int m, int n) {
int prev[] = new int[n];
int curr[] = new int[n];
for (int j = 0; j < n; j++) {
prev[j] = 1;
}
for (int i = 1; i < m; i++) {
curr[0] = 1;
for (int j = 1; j < n; j++) {
curr[j] = curr[j - 1] + prev[j];
}
prev = curr;
}
return prev[n - 1];
}
}class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> prev(n, 0);
vector<int> curr(n, 0);
for (int j = 0; j < n; j++) {
prev[j] = 1;
}
for (int i = 1; i < m; i++) {
curr[0] = 1;
for (int j = 1; j < n; j++) {
curr[j] = curr[j - 1] + prev[j];
}
prev = curr;
}
return prev[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[-1]function uniquePaths(m, n) {
const prev = new Array(n).fill(1);
const curr = new Array(n).fill(0);
for (let i = 1; i < m; i++) {
curr[0] = 1;
for (let j = 1; j < n; j++) {
curr[j] = curr[j - 1] + prev[j];
}
for (let j = 0; j < n; j++) prev[j] = curr[j];
}
return prev[n - 1];
}Edge Cases to Watch
- m = 1 or n = 1 (only a single row or column; robot has only 1 path straight to end, returns 1)
- m = 3, n = 7 (standard LeetCode test case; returns 28)
- Square grids (e.g. m = 3, n = 3; returns 6)
Algorithmic Pattern
View Pattern Guide →
Master the Dynamic Programming Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Dynamic Programming pattern.
Framework: Dynamic Programming • Interview Prep: Tested at FAANG •
Explore all Dynamic Programming problems & invariants →
How to Recognize This Pattern
- Grid path counting
- Only move right or down
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(n)
Tags
Math DP Combinatorics
Frequently Asked Questions
What is the optimal time and space complexity for Unique Paths?
The optimal solution for Unique Paths achieves O(m × n) runtime complexity and requires O(n) auxiliary space. Time complexity is O(m * n) since every grid cell is visited once. Space complexity is O(n) using a rolling 1D row array.
How do I identify that Unique Paths requires the Dynamic Programming pattern?
In technical interviews, look for key problem signals: Grid path counting; Only move right or down. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Dynamic Programming strategy.
What critical edge cases must be handled in Unique Paths?
Essential edge cases to verify include: m = 1 or n = 1 (only a single row or column; robot has only 1 path straight to end, returns 1); m = 3, n = 7 (standard LeetCode test case; returns 28); Square grids (e.g. m = 3, n = 3; returns 6). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Unique Paths?
Unique Paths is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google, Apple.