Unique Paths
A robot starts in the top-left cell of a grid with m rows and n columns and has to reach the bottom-right cell. Each move takes it one cell to the right or one cell down. Return the number of different paths it can take.
Function
- minteger
- the number of rows in the grid
- ninteger
- the number of columns in the grid
- Returnsinteger
- the number of different paths from the top-left cell to the bottom-right cell
Constraints
1 ≤ m, n ≤ 100- The answer is at most
2 × 109, so it fits in a signed 32-bit integer.
Examples
- Input
- m = 3n = 4
- Output
- 10
- Explanation
- Every path makes 2 moves down and 3 moves right, 5 moves in all. A path is fixed by which 2 of the 5 moves go down, and there are 10 ways to pick them.
- Input
- m = 1n = 6
- Output
- 1
- Explanation
- With a single row the robot can only move right 5 times, so there is exactly one path.
- Input
- m = 4n = 5
- Output
- 35
- Explanation
- Each path has 3 moves down and 4 moves right. Picking which 3 of the 7 moves go down gives 7 × 6 × 5 / 6 = 35 paths.
Follow-up
For a 100 × 100 grid the answer has 59 digits. How would you return it modulo 10^9+7 with the formula, when dividing by i no longer works?
Hints
Open them one at a time. Each one gives away a little more.
Where could the robot have been right before it stepped into a cell?
The paths into a cell are the paths into the cell above plus the paths into the cell to its left. The top row and the left column have exactly one path each.
Fill the counts row by row, left to right, keeping a single row of numbers. Or count orders of moves directly: a path is a choice of which
m-1of them+n-2moves go down.
Solution
Listing the paths is hopeless: a 17 × 17 grid has 601,080,390 of them. Count instead. The paths into a cell are those into the cell above plus those into the cell on its left, which fills a table in one pass. And a path is only an order of downs and rights, which gives a closed formula.
Count every path with recursion
Correct, but does not finish on the largest tests
Intuition
The robot's last move came either down from the cell above or right from the cell to the left. So uniquePaths(m, n) = uniquePaths(m-1, n) + uniquePaths(m, n-1), and a grid with one row or one column has exactly 1 path. Every path ends with exactly one of the two moves, so each is counted once.
Every path ends in a base case that returns 1, so the number of calls is at least the answer: a 17 × 17 grid takes more than 600 million calls. The same smaller grids are worked out again and again.
Algorithm
- If
mornis 1, return 1: the only path is a straight line. - Otherwise count the paths whose last move goes down,
uniquePaths(m-1, n). - Count the paths whose last move goes right,
uniquePaths(m, n-1). - Return their sum.
def uniquePaths(m, n):
# One row or one column: the only path is a straight line
if m == 1 or n == 1:
return 1
# The last move came down from the row above or right from the column before
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)Fill the grid one row at a time
Intuition
The recursion keeps asking about the same m × n cells. Count each cell once, in an order where its inputs are ready.
State: paths[r][c] is the number of paths from the top-left cell to row r, column c. Recurrence: paths[r][c] = paths[r-1][c] + paths[r][c-1], the arrivals from above plus those from the left. Base cases: every cell of the top row and the left column has 1 path. Order: row by row, left to right. For m = 3, n = 4 the rows are 1 1 1 1, 1 2 3 4, 1 3 6 10, and the answer is 10.
The fill reads only the row above, so keep one row. Before you update row[c] it still holds the count from above, and row[c-1] already holds the new count to its left, so row[c] += row[c-1] is the whole recurrence in O(n) memory.
Algorithm
- Make
rowwithnentries, all 1: the top row. - Repeat
m-1times, once for each row below the top. - In each row, for
cfrom 1 ton-1, addrow[c-1]torow[c].row[0]stays 1: that is the left column. - Return
row[n-1].
def uniquePaths(m, n):
# row[c] counts the paths into column c of the current row.
# The top row is all 1s: the only way along it is straight right.
row = [1] * n
for _ in range(m - 1):
for c in range(1, n):
# Paths from above (the old row[c]) plus paths from the left (the new row[c-1])
row[c] += row[c - 1]
return row[n - 1]Count the moves with a binomial coefficient
Intuition
Every path makes m-1 moves down and n-1 moves right, m+n-2 moves in some order. Every order is a valid path: it never makes more than m-1 downs or n-1 rights, so it never leaves the grid. A path is therefore a choice of which m-1 moves go down, and the answer is C(m+n-2, m-1).
Build the coefficient without factorials. With N = m+n-2 and k = min(m, n)-1, multiply by N-k+i and then divide by i, for i from 1 to k. After step i the value is C(N-k+i, i), a whole number, so every division is exact. For m = 3, n = 4: 1 × 4 / 1 = 4, then 4 × 5 / 2 = 10. Choosing along the shorter side keeps the loop at 99 steps or fewer.
Algorithm
- Set
N = m+n-2, the number of moves, andk = min(m, n)-1. - Start a 64-bit count at 1.
- For
ifrom 1 tok, multiply the count byN-k+i, then divide it byi. - Return the count.
def uniquePaths(m, n):
# A path is m+n-2 moves; count the ways to choose which of them go down.
# Choose along the shorter side so the loop stays short.
moves = m + n - 2
k = min(m, n) - 1
count = 1
for i in range(1, k + 1):
# count goes from C(moves-k+i-1, i-1) to C(moves-k+i, i); the division is exact
count = count * (moves - k + i) // i
return count
Pitfalls and edge cases
- Computing
(m+n-2)!and dividing by the other two factorials. 21! is already past the 64-bit range, andm+n-2reaches 105 in a 100 × 7 grid. - Dividing before you multiply, as in
count / i * (N-k+i).countis not always a multiple ofi, so the division truncates. - Keeping the running product in 32 bits. Before the last division it is
ktimes the answer: 16 × 601,080,390, about 9.6 × 10^9, for a 17 × 17 grid. - Starting the top row or the left column at 0 instead of 1. Every cell becomes 0, though a grid with one row or one column has exactly 1 path.
Frequently asked questions3
What is the time complexity of Unique Paths?
The dynamic programming table takes O(m × n) time, and O(n) space when you keep one row. The binomial formula takes O(min(m, n)) time and O(1) space. Plain recursion makes at least as many calls as there are paths, which is exponential in m + n.
How do you solve Unique Paths when some cells are blocked?
Use the same table, and set the count of a blocked cell to 0 so no path passes through it. The top row and the left column stop being all 1s: every cell after a blocked one in the top row has 0 paths. The formula no longer works, because it assumes every order of moves is allowed.
Why does the Unique Paths table match Pascal's triangle?
Each cell adds the cell above and the cell to its left, which is the rule that builds Pascal's triangle, read along its diagonals. The cell at row r and column c holds C(r+c, r), so the bottom-right cell holds C(m+n-2, m-1), the binomial formula.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def uniquePaths(m, n):
# Write code hereTest #1
Test #2
Test #3
Arguments
m = 3 n = 4
Expected Output
10