Unique Paths
find all the unique path to reach the end of matrix
Unique Paths
Problem Statement
There is a robot on an m x n grid. The robot starts at the top-left corner (grid[0][0]), and tries to reach the bottom-right corner (grid[m-1][n-1]). The robot can only move down or right at any point.
Given two integers, m and n, return the number of unique paths the robot can take to reach the bottom-right corner.
Note: The test cases are designed so that the answer will always be less than or equal to
2 × 10⁹.
Examples
Example 1
Input: m = 3, n = 7
Output: 28
Example 2
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are 3 total ways to reach the bottom-right corner:
- Right → Down → Down
- Down → Down → Right
- Down → Right → Down
Constraints
1 ≤ m, n ≤ 100
Solution
We work backward from the bottom-right corner toward the top-left. If we reach the start, that counts as 1 valid path. If we go out of bounds, that path isn't valid, so it counts as 0. To find all possible paths, we recursively explore moving up and left.
Brute Force
var uniquePaths = function(m, n) {
function recurr(i, j) {
if (i == 0 && j == 0) {
return 1;
}
if (i < 0 || j < 0) {
return 0;
}
let up = recurr(i - 1, j);
let left = recurr(i, j - 1);
return left + up;
}
return recurr(m - 1, n - 1);
};
Memoization (Top-Down)
Same recursive logic, but we store each cell's result in a memo grid the first time we calculate it, so we avoid repeating the same work.
var uniquePaths = function (m, n) {
let memo = Array.from({ length: m }, () => Array(n).fill(-1));
function recurr(i, j, memo) {
if (i == 0 && j == 0) {
return memo[i][j] = 1;
}
if (i < 0 || j < 0) {
return 0;
}
if (memo[i][j] !== -1) {
return memo[i][j];
}
let left = recurr(i - 1, j, memo);
let right = recurr(i, j - 1, memo);
memo[i][j] = left + right;
return memo[i][j];
}
return recurr(m - 1, n - 1, memo);
};
Tabulation (Bottom-Up)
Instead of recursing from the end, we build the answer forward, starting from the top-left cell and working toward the bottom-right.
var uniquePaths = function (m, n) {
let memo = Array.from({ length: m }, () => Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i == 0 && j == 0) {
memo[i][j] = 1;
} else {
let up = 0;
let left = 0;
if (i > 0) {
up = memo[i - 1][j];
}
if (j > 0) {
left = memo[i][j - 1];
}
memo[i][j] = left + up;
}
}
}
return memo[m - 1][n - 1];
};
Space Optimization
Since each row only ever depends on the row directly above it, we don't need to store the entire grid. We just keep track of the previous row (prev) and build the current row (curr) based on it.
var uniquePaths = function (m, n) {
let prev = [];
for (let i = 0; i < m; i++) {
let curr = [];
for (let j = 0; j < n; j++) {
if (i == 0 && j == 0) {
curr[j] = 1;
} else {
let up = 0;
let left = 0;
if (i > 0) {
up = prev[j];
}
if (j > 0) {
left = curr[j - 1];
}
curr[j] = left + up;
}
}
prev = curr;
}
return prev[n - 1];
};
.