Unique Paths in a Grid

Count the number of distinct paths from top-left to bottom-right moving only down or right.

dynamic-programming grid counting combinatorics

Write a function `unique_paths(m: int, n: int) -> int` that returns the number of distinct paths from the top-left cell to the bottom-right cell of an `m` x `n` grid. On each move you can only go **down** or **right**. The grid has `m` rows and `n` columns, and the start is at (0,0) and the end is at (m-1, n-1). The result is an integer (Python's arbitrary-precision int), and it is guaranteed that for the given constraints the exact value fits within a standard integer in Python.

**Input constraints:**
- `0 <= m <= 100`
- `0 <= n <= 100`
- If either `m` or `n` is 0, return 0 (no cells).
- The result may exceed 64-bit but Python handles large integers natively.

**Implementation requirement:** You should implement `unique_paths(m, n)` exactly as described. The function should return the exact number without modulo.

Constraints

0 <= m, n <= 100. Time complexity: O(m * n) or O(min(m,n)) space. The answer can be large but fits in Python's integer type.

Example

>>> unique_paths(3, 2)
3
>>> unique_paths(3, 7)
28
>>> unique_paths(0, 5)
0
>>> unique_paths(1, 1)
1

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of dynamic programming: the number of paths to a cell equals paths from its top plus paths from its left.

Use a 1D array to compress space instead of a full 2D table.

Alternatively, use the combinatorial formula C(m+n-2, m-1) with math.comb.

Handle edge cases where m == 0 or n == 0 (return 0) and m == 1 or n == 1 (return 1).

Test Results

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