Unique Paths in a Grid

Count the number of unique paths from the top-left corner to the bottom-right corner of a grid, moving only right and down.

dynamic-programming grid counting combinatorics

You are given a grid with m rows and n columns. You start at the top-left cell (0, 0) and you want to reach the bottom-right cell (m-1, n-1). At each step, you may only move either right or down. Write a function `unique_paths(m: int, n: int) -> int` that returns the number of distinct paths from the start to the goal. The grid dimensions m and n are positive integers. The answer will fit within a 64-bit signed integer for the given constraints.

Constraints

1 ≤ m, n ≤ 20. The answer is guaranteed to be less than 2^63. The function should be efficient enough for these bounds; O(m*n) time and O(n) extra space is acceptable.

Example

>>> unique_paths(1, 1)
1
>>> unique_paths(3, 2)
3
>>> unique_paths(3, 7)
28
>>> unique_paths(10, 10)
48620

15 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of a simple recurrence: the number of paths to a cell is the sum of paths from the cell above and the cell to the left.

Use a 1D array to store the number of paths for the current row to save space.

Simplify by noticing the answer is a binomial coefficient C(m+n-2, m-1). You can compute it iteratively to avoid overflow.

Edge case: when either dimension is 1, there is exactly 1 path.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.