Description
Count paths from the top-left to bottom-right cell of an m by n grid, moving only right or down. Dimensions are positive.
Solution
def unique_paths(m, n):
row = [1]*n
for _ in range(1,m):
for c in range(1,n):
row[c] += row[c-1]
return row[-1]Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[2,3]- Output
3
Place the one downward move in any of three positions.
Example 2
- Input
[1,5]- Output
1
There is only one row.
Example 3
- Input
[3,3]- Output
6
Choose two downward moves among four total moves.
Approach
A cell's path count is the sum from above and left. Update a single row in place.
Time & space
O(m n) time; O(n) auxiliary space, where m is the number of rows and n the number of columns.