FAANGPrep Sprint
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
EACH CELL COUNTS THE PATHS THAT REACH IT · OUTLINED = THE CELL ABOVE AND THE CELL LEFT, WHICH ADD
NEXT ROW
0
1
2
0
1
2
grid
3 × 3
filled
0/9
Answer
—
the rule
dp[0][j] = dp[i][0] = 1
Row 0
Next
(0, 0) is on the top row, so there is one way to reach it — go straight. dp[0][0] = 1
grid
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.