> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Unique Paths Python Solution with Tests

> Tested Python solution for LeetCode 62 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 62, Medium. Topics: Math, Dynamic Programming, Combinatorics. [View on LeetCode](https://leetcode.com/problems/unique-paths/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 62   # by problem number
lcpy gen -s unique_paths   # by problem name
```

## Problem

There is a robot on an `m x n` grid. The robot is initially located at the **top-left corner** (i.e., `grid[0][0]`). The robot tries to move to the **bottom-right corner** (i.e., `grid[m - 1][n - 1]`). The robot can only move either down or right at any point in time.

Given the two integers `m` and `n`, return *the number of possible unique paths that the robot can take to reach the bottom-right corner*.

The test cases are generated so that the answer will be less than or equal to `2 * 10^9`.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png)

```
Input: m = 3, n = 7
Output: 28
```

```
Input: m = 3, n = 2
Output: 3
```

**Explanation:** From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

### Constraints

* 1 \<= m, n \<= 100

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/unique_paths/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/unique_paths/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Dynamic Programming
    # Time: O(m * n)
    # Space: O(min(m, n))
    def unique_paths(self, m: int, n: int) -> int:
        if m > n:
            m, n = n, m
        dp = [1] * m
        for _ in range(1, n):
            for j in range(1, m):
                dp[j] += dp[j - 1]
        return dp[m - 1]


class SolutionMath:
    # Math solution: C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!)
    # Time: O(min(m, n))
    # Space: O(1)
    def unique_paths(self, m: int, n: int) -> int:
        # Total moves: (m-1) right + (n-1) down = m+n-2
        # Choose (m-1) positions for right moves out of (m+n-2) total
        if m > n:
            m, n = n, m  # Optimize for smaller factorial

        result = 1
        for i in range(m - 1):
            result = result * (n + i) // (i + 1)
        return result
```

## Complexity

| Time      | Space        |
| --------- | ------------ |
| O(m \* n) | O(min(m, n)) |

## Tags

[Grind 75](/catalog/grind-75), [Grind](/catalog/grind), [Blind 75](/catalog/blind-75), [NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).