Unique Paths
Count the paths from the top-left to the bottom-right of an m × n grid when you may only move right or down.
Progress cannot be saved in this browser, so completed lessons will reset when you leave.
Lesson notes
Try it before you watch
Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.
Reveal the key idea
The number of paths to a cell is the sum of the paths to the cell above and the cell to the left. A single row of the table is enough.
Pattern: Dynamic programming. Define a state, write the recurrence between states, and compute each state only once.
Complexity
| Measure | Bound |
|---|---|
| Time | O(m · n) |
| Extra space | O(n) |
Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.