# Unique Paths

- **Canonical ID**: `unique-paths`
- **Canonical URL**: https://dsacheatsheet.com/problems/unique-paths
- **Difficulty**: medium
- **Patterns**: 2D DP
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/unique-paths/

## 1. Core Invariant / The Trick

Rolling 1D row of width `n` initialized to `1`: `dp[j] += dp[j - 1]` combines ways from top (`prev dp[j]`) and left (`updated dp[j-1]`). Or closed-form binomial `C(m + n - 2, min(m, n) - 1)`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(M * N)`
- **Space Complexity**: `O(N)`
- **Proof**: Wait: closed-form `C(m+n-2, min(m,n)-1)` runs in O(min(M, N)) time and O(1) space; rolling 1D DP handles obstacles smoothly in follow-ups.

## 3. Minimal Idiomatic Code

### Python
```python
def uniquePaths(m: int, n: int) -> int:
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]
    return row[-1]
```

### TypeScript
```typescript
export function uniquePaths(m: number, n: number): number {
  const row = new Array(n).fill(1);
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) row[c] += row[c - 1];
  }
  return row[n - 1];
}
```

### C++
```cpp
int uniquePaths(int m, int n) {
    vector<int> row(n, 1);
    for (int r = 1; r < m; ++r)
        for (int c = 1; c < n; ++c) row[c] += row[c - 1];
    return row[n - 1];
}
```

### Java
```java
int uniquePaths(int m, int n) {
    int[] row = new int[n];
    Arrays.fill(row, 1);
    for (int r = 1; r < m; r++)
        for (int c = 1; c < n; c++) row[c] += row[c - 1];
    return row[n - 1];
}
```

### Go
```go
func uniquePaths(m, n int) int {
    row := make([]int, n)
    for i := range row { row[i] = 1 }
    for r := 1; r < m; r++ {
        for c := 1; c < n; c++ { row[c] += row[c-1] }
    }
    return row[n-1]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Overflow on intermediate factorial `(m+n-2)!` if computing closed-form naively instead of multiplicative loop or DP.

### Follow-ups
- Unique Paths II adds obstacles (`obstacleGrid[r][c] == 1 -> dp[c] = 0`).