Unique Paths
A robot stands in the top left cell of a grid with m rows and n columns. It can move one cell right or one cell down at a time. It wants to reach the bottom right cell.
Return the number of different paths the robot can take. The answer is guaranteed to be at most 2,000,000,000.
Examples
Start at S in the top left corner and finish at F in the bottom right corner.
Input m = 3, n = 7
Output 28
Start at S in the top left corner and finish at F in the bottom right corner.
Input m = 3, n = 2
Output 3
Right then down then down, down then right then down, down then down then right.
Start at S in the top left corner and finish at F in the bottom right corner.
Input m = 1, n = 5
Output 1
A single row has one path.
Constraints
- 1 <= m, n <= 100, and the answer is at most 2,000,000,000
Stuck? Take one hint at a time
Common mistakes
- Using the same recurrence but starting the first row and column at 0, which makes every cell 0.
- Calculating factorials of m + n - 2 directly, which overflows for even modest grids.
- Dividing too early in the binomial loop, so the integer division loses a fraction. Multiply first, then divide.
- Mixing up rows and columns: the moves are m - 1 down and n - 1 right, not the other way round.
Questions an interviewer may ask next
- Some cells are blocked by obstacles. Count the paths that avoid them. (The table version: a blocked cell has 0 ways.)
- The robot may also move diagonally. What changes in the recurrence?
- Count the paths that pass through a given cell. (Multiply the counts of the two halves.)
- Find the path with the smallest sum of cell values. (The same table, with min and costs.)
m
3
n
7
Expected output
28
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.