Unique Paths
Count the distinct routes a robot can take from the top-left cell of an m x n grid to the bottom-right cell when every step goes one cell down or one cell right.
Examples
Every path makes 2 down moves and 6 right moves in some order: C(8, 2) = 28.
Down-Down-Right, Down-Right-Down and Right-Down-Down.
A single row leaves no choice — the robot can only move right.
Problem Understanding
We need to count how many ways to reach (m-1, n-1) from (0, 0) moving only Right or Down.
Example: m = 3, n = 2
- Right -> Down -> Down
- Down -> Down -> Right
- Down -> Right -> Down
- Output: 3
Algorithm Strategy
The robot moves only right or down, so the last move into (i, j) came from the cell above or the cell to the left — and from nowhere else.
Those two sets of paths are disjoint, because they differ in that final move, and together they are every path to (i, j). So the counts add.
Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]
Base cases: the top row and the left column are all 1 — there is only one way to reach them, which is to go straight. Filling row by row means both cells a write depends on are already written.
Interactive Visualization
Every cell counts the paths that reach it. Watch the two outlined cells — the one above and the one to the left — and the fill that adds them: that highlight is the recurrence.
Try 1 row: the recurrence never runs, because every cell is a base case.
Dry Run
m=3, n=3
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 1 | 1 | 1 (Base Case) |
| 1 | 1 | 1+1=2 |
2+1=3 |
| 2 | 1 | 2+1=3 |
3+3=6 |
Edge Cases & Common Mistakes
Common pitfalls:
One row or one column is all base case. The recurrence never runs, and the answer is 1. If your loop starts at 1 instead of guarding inside, this is the case that breaks.
The grid is m by n, and the answer is at dp[m-1][n-1]. Swapping m and n gives the same count — the formula is symmetric — but indexing with the wrong one walks off the end of a row.
Big grids overflow 32-bit ints. The count is C(m+n-2, m-1), which passes 2³¹ well before a 20 by 20 grid. LeetCode keeps m and n under 100 and the answer under 2·10⁹, which just fits.
Solution
One pass over the grid, with the base cases guarded inside the loop — the lines light up as the figure above steps.
Unique Paths Code
1var uniquePaths = function(m, n) {2 const dp = Array.from({ length: m }, () => new Array(n).fill(0));3 for (let i = 0; i < m; i++) {4 for (let j = 0; j < n; j++) {5 if (i === 0 || j === 0) {6 dp[i][j] = 1;7 continue;8 }9 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];10 }11 }12 return dp[m - 1][n - 1];13};