A robot sits in the top-left cell of an m x n grid. It can move only right or down, one cell at a time, and wants to reach the bottom-right cell.
Return the number of distinct paths the robot can take.
Example
Constraints
- 1 <= m, n <= 100
- The answer fits in a 32-bit signed integer.
Intuition
A first pass just recurses on the two moves available at every cell — step down, or step right — and adds up however many complete paths each choice leads to, until the robot reaches the destination or falls off the edge of the grid.
function uniquePaths(m, n) {
// Count the paths from (row, col) to the bottom-right corner.
function solve(row, col) {
// Reached the destination — this is one complete path.
if (row === m - 1 && col === n - 1) return 1;
// Walked off the bottom or right edge — this path is invalid.
if (row >= m || col >= n) return 0;
// Every path from here either steps down first or steps right first.
return solve(row + 1, col) + solve(row, col + 1);
}
return solve(0, 0);
}This is O(2^(m+n)) — every cell branches the recursion into two more calls, and the same cell gets revisited independently by every route that reaches it (down-then-right and right-then-down both land on the same next cell, and each re-derives its remaining path count from scratch). Can we do better?
The key observation: solve(row, col) — the number of paths from (row, col) to the destination — depends only on that cell, never on the route taken to reach it. Once it's answered, it never changes, so it's only worth solving once. That's the overlapping-subproblems signature dynamic programming exists for.
Flip the recursion around and fill it bottom-up instead: let dp[i][j] be the number of paths from the top-left corner to (i, j). Every cell is entered either from above or from the left, so dp[i][j] = dp[i-1][j] + dp[i][j-1]. The entire top row and entire left column only have one possible route each — straight right, or straight down — so they're seeded to 1 before the fill starts.
Each row of dp only ever reads the row directly above it and the cell to its own left, so nothing older than "the row above" is ever needed again. The stored solution exploits that and never keeps the full table — it rolls a single array row of length n forward, one grid row at a time: row[j] += row[j - 1] folds together dp[i-1][j] (still sitting in row[j] from the previous pass) and dp[i][j-1] (already overwritten earlier in this pass, so row[j-1] already holds the current row's value). The diagram below fills the full 2-D table to make the recurrence visible; the code just folds it into that one rolling row.
Walking it through:
dp[i][j] = paths to reach (i, j), for a 3x4 grid (m = 3, n = 4)
The top row and left column each have exactly one route — straight right, or straight down — so they're seeded to 1 before anything is computed.
Every interior cell just adds the count above it to the count on its left — two ways converge here for the first time.
Row 1 fills left to right the same way; by its last cell, 4 routes have already converged.
Row 2 reuses row 1's just-finished values the same way; dp[2][1] = 3 was filled in just before this step, so dp[2][2] adds 3 (from above) and 3 (from the left) to get 6.
The bottom-right cell sums every path that could have arrived from above or from the left — 10 distinct routes in total.
Optimization
Rolling 1-D DP
Each cell's path count is the sum of the cell above and the cell to its left, with the whole top row and left column equal to 1. Sweeping row by row, a single array of length n suffices: row[j] += row[j-1] updates "above + left" in place.
O(m·n) time, O(n) space.
function uniquePaths(m, n) {
// row[j] = dp[i][j] for the row currently in progress; row 0 is all 1s (only one route: always right).
const row = new Array(n).fill(1);
for (let i = 1; i < m; i++) {
// Column 0 stays 1 (the only route down the left edge), so start at j = 1.
for (let j = 1; j < n; j++) {
// row[j] is still dp[i-1][j]; row[j-1] was already overwritten this pass, so it's already dp[i][j-1].
row[j] += row[j - 1];
}
}
return row[n - 1];
}Complexity analysis
Time complexity: O(m·n). Here's why:
- The fill (whether kept as a full table or rolled into one row) computes exactly one value per cell of the m×n grid.
- Each cell's value is a single addition of two already-known cells — O(1) work.
So the whole fill is O(m·n) — down from the brute force's exponential O(2^(m+n)), since each cell is now computed exactly once instead of re-derived by every route that passes through it.
Space complexity: O(n). Here's why:
- The stored solution keeps only one rolling row of length n (the column count), never the full m×n table.
- There's no recursion, so no call stack to add on top — unlike the brute force's O(m+n)-deep call stack.
A full 2-D table would cost O(m·n); rolling it down to a single row that gets overwritten row by row drops that to O(n).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| m = 1, n = 1 | 1 | Robot starts on the destination cell — one path, the empty one. |
| m = 1, n = 8 | 1 | A single row — the robot has no choice but to move right the whole way; exactly one path. |
| m = 9, n = 1 | 1 | A single column — the robot has no choice but to move down the whole way; exactly one path. |
| m = 5, n = 5 | 70 | Square grid — exercises the general recurrence over several rows and columns. |
| m = 2, n = 5 | 5 | Rectangular grid with more columns than rows — a smaller, easily hand-checked general case. |
Try it yourself
Write your solution against the real judge before checking the reference.