LeetCode 62 ·
Medium
Unique Paths
Count the paths from the top-left to bottom-right of an m×n grid moving only right or down.
Try it
Step through the core mechanic. The simulator below runs the dynamic programming shape this problem is built on.
Interactive · Unique Paths — dp[i][j] dp[i][j] = dp[i−1][j] + dp[i][j−1]
| c0 | c1 | c2 | c3 | |
|---|---|---|---|---|
| r0 | 1 | 1 | 1 | 1 |
| r1 | 1 | · | · | · |
| r2 | 1 | · | · | · |
base row & column seeded
The approach
paths(i,j) = paths(i−1,j) + paths(i,j−1), with the first row and column all 1. Fill the grid; one row of rolling state gives O(n) space. (Closed form: a binomial coefficient.)
| Aspect | Value |
|---|---|
| Pattern | Dynamic programming |
| Recognise it by | Count grid paths moving only right/down. |
| Time complexity | O(mn) |
| Space complexity | O(n) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.