62. Unique Paths
A walker stands on the top-left cell of an m x n grid and wants to reach the bottom-right cell. At every step it may move only one cell right or one cell down — never left, up, or diagonally.
Your function receives the two integers m (rows) and n (columns) and must return the number of distinct routes from the top-left corner to the bottom-right corner.
Two routes are distinct if they differ in at least one step. The answer is guaranteed to fit in a 32-bit unsigned range (at most 2 * 10^9).
Example 1:
Input: m = 3, n = 7
Output: 28
Explanation: Every route uses exactly 2 downs and 6 rights in some order; there are 28 ways to arrange them.
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation: The three routes are down-down-right, down-right-down, and right-down-down.
Constraints:
- 1 ≤ m, n ≤ 100
- The answer is at most 2 * 10⁹.
Hints:
The only ways to arrive at a cell are from the cell above it or the cell to its left, so paths(i, j) = paths(i-1, j) + paths(i, j-1). Cells in the first row or first column can be reached exactly one way.
You never need more than the previous row — keep a single 1D array and update it left to right.
Every route is a sequence of exactly m-1 downs and n-1 rights. Counting the arrangements of that sequence is a single binomial coefficient: C(m+n-2, m-1).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: m = 3, n = 7
Expected output: 28