# Unique Paths
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/unique-paths)
Canonical: https://scaleengineer.com/dsa/problems/unique-paths
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Cisco](https://scaleengineer.com/companies/cisco), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [Roblox](https://scaleengineer.com/companies/roblox), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [tcs](https://scaleengineer.com/companies/tcs), [Coupang](https://scaleengineer.com/companies/coupang), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Zomato](https://scaleengineer.com/companies/zomato), [Grammarly](https://scaleengineer.com/companies/grammarly)
---
## 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 * 109`.

**Example 1:**

![](https://assets.glich.co/dsa/unique-paths/image0.png) 

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

**Example 2:**

**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`

# Approaches
## Brute-Force Recursion
This approach directly translates the problem's definition into a recursive function. The number of paths to a cell `(r, c)` is the sum of paths from the cell below `(r+1, c)` and the cell to the right `(r, c+1)`. The recursion starts from `(0, 0)` and has a base case when it reaches the destination `(m-1, n-1)`.
**Time:** O(2^(m+n)) · **Space:** O(m + n)
**Pros:** Simple to understand and implement.; Directly models the problem statement.
**Cons:** Extremely inefficient due to a massive number of redundant calculations (overlapping subproblems).; Will result in a 'Time Limit Exceeded' error for all but the smallest grid sizes.
### Explanation
We define a recursive function, say `countPaths(r, c)`, which calculates the number of unique paths from the cell `(r, c)` to the destination `(m-1, n-1)`. The function works as follows:

- **Base Cases:**
  - If the robot reaches the destination (`r == m-1` and `c == n-1`), it has found one valid path. So, we return 1.
  - If the robot goes out of the grid boundaries (`r >= m` or `c >= n`), it's an invalid path. So, we return 0.

- **Recursive Step:**
  - For any other cell `(r, c)`, the robot can either move down to `(r+1, c)` or right to `(r, c+1)`.
  - The total number of paths from `(r, c)` is the sum of paths from these two subsequent cells: `countPaths(r+1, c) + countPaths(r, c+1)`.

The initial call to the function will be `countPaths(0, 0)`. This method suffers from a major drawback: it recomputes the number of paths for the same cells multiple times, leading to an exponential number of calls.

```java
public class Solution {
    public int uniquePaths(int m, int n) {
        return countPaths(0, 0, m, n);
    }

    private int countPaths(int r, int c, int m, int n) {
        // Base case: out of bounds
        if (r >= m || c >= n) {
            return 0;
        }
        // Base case: reached destination
        if (r == m - 1 && c == n - 1) {
            return 1;
        }
        // Recursive step
        return countPaths(r + 1, c, m, n) + countPaths(r, c + 1, m, n);
    }
}
```
### Algorithm
- `1. Define a recursive function `countPaths(r, c)` that returns the number of paths from cell `(r, c)` to the destination.`
- `2. **Base Case 1:** If the robot goes out of bounds (`r >= m` or `c >= n`), it's an invalid path. Return 0.`
- `3. **Base Case 2:** If the robot reaches the destination (`r == m - 1` and `c == n - 1`), it has found one valid path. Return 1.`
- `4. **Recursive Step:** For any other cell, the number of paths is the sum of paths from moving down and paths from moving right. Return `countPaths(r + 1, c) + countPaths(r, c + 1)`.`
- `5. The initial call is `countPaths(0, 0)`.`

## Dynamic Programming (Tabulation)
This approach improves upon the brute-force recursion by storing the results of subproblems to avoid recomputation, a technique known as dynamic programming. We can use either a top-down (memoization) or a bottom-up (tabulation) approach. Both have the same time and space complexity, but the bottom-up approach is often slightly more efficient as it avoids recursion overhead.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Much more efficient than brute-force.; Avoids recomputing subproblems, guaranteeing a solution within time limits for the given constraints.
**Cons:** Uses O(m*n) space, which can be substantial for large grids.
### Explanation
The number of ways to reach cell `(i, j)` is the sum of the ways to reach the cell above it, `(i-1, j)`, and the cell to its left, `(i, j-1)`. This gives us the recurrence relation: `dp[i][j] = dp[i-1][j] + dp[i][j-1]`.

We use a bottom-up (tabulation) approach:
- We create a 2D DP table `dp[m][n]`.
- `dp[i][j]` will store the number of unique paths to reach cell `(i, j)`.
- **Initialization:** Since the robot can only move right or down, all cells in the first row (`dp[0][j]`) and the first column (`dp[i][0]`) have only one way to be reached. So, we initialize `dp[0][j] = 1` and `dp[i][0] = 1` for all valid `i` and `j`.
- **Iteration:** We then iterate through the rest of the grid, from `(1, 1)` to `(m-1, n-1)`, and fill the table using the recurrence `dp[i][j] = dp[i-1][j] + dp[i][j-1]`.
- The final answer is the value in the bottom-right cell, `dp[m-1][n-1]`.

```java
public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        // Initialize the first row and first column to 1
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        // Fill the rest of the DP table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
}
```
### Algorithm
- `1. Create a 2D array `dp` of size `m x n`.`
- `2. Initialize the first row (`dp[0][j]`) and the first column (`dp[i][0]`) with 1s, as there's only one way to reach these cells.`
- `3. Iterate from `i = 1` to `m-1` and `j = 1` to `n-1`.`
- `4. For each cell `(i, j)`, calculate `dp[i][j] = dp[i-1][j] + dp[i][j-1]`.`
- `5. Return the value at `dp[m-1][n-1]`.`

## Space-Optimized Dynamic Programming
This approach optimizes the space complexity of the standard DP solution. When calculating the number of paths for the current row, we only need the values from the previous row. Therefore, we don't need to store the entire 2D DP table. We can use a 1D array to store the results of the previous row, reducing space complexity.
**Time:** O(m * n) · **Space:** O(n)
**Pros:** Maintains the efficient O(m*n) time complexity.; Significantly reduces space complexity compared to the standard DP approach.
**Cons:** The logic can be slightly less intuitive to grasp than the 2D DP table approach.
### Explanation
We observe that to compute the values for the current row `i`, we only need values from the previous row `i-1`. This allows us to reduce the space from a 2D array to a 1D array.

- We use a 1D array `dp` of size `n`. This array will represent a row in the grid.
- **Initialization:** We initialize the `dp` array with all 1s. This represents the first row of the grid, where there's only one way to reach each cell.
- **Iteration:** We then loop for the remaining `m-1` rows. In an inner loop, we iterate through the columns from `j = 1` to `n-1`.
- The update rule becomes `dp[j] = dp[j] + dp[j-1]`. Here, `dp[j]` on the right side represents the value from the previous row (`dp[i-1][j]`), and `dp[j-1]` represents the newly computed value from the current row's previous column (`dp[i][j-1]`).
- After iterating through all the rows, the last element of the `dp` array, `dp[n-1]`, will hold the final answer.

```java
public class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        // Initialize the array with 1s
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }

        // Iterate through the rows (starting from the second row)
        for (int i = 1; i < m; i++) {
            // Iterate through the columns (starting from the second column)
            for (int j = 1; j < n; j++) {
                // dp[j] holds the value from the previous row (paths from above)
                // dp[j-1] holds the value from the current row's previous column (paths from left)
                dp[j] = dp[j] + dp[j-1];
            }
        }

        return dp[n - 1];
    }
}
```
### Algorithm
- `1. Create a 1D array `dp` of size `n` (or `min(m, n)` for optimization).`
- `2. Initialize all elements of `dp` to 1.`
- `3. Iterate from `i = 1` to `m-1` (for rows).`
- `4. Inside this loop, iterate from `j = 1` to `n-1` (for columns).`
- `5. Update `dp[j] = dp[j] + dp[j-1]`.`
- `6. After the loops, return `dp[n-1]`.`

## Combinatorial Approach
This is the most efficient approach and involves looking at the problem from a mathematical perspective. Any path from the top-left to the bottom-right corner consists of a fixed number of 'down' moves and 'right' moves. The problem then becomes counting the number of unique sequences of these moves.
**Time:** O(min(m, n)) · **Space:** O(1)
**Pros:** Most efficient solution in terms of both time and space.; Elegant mathematical solution that avoids grid traversal.
**Cons:** Requires understanding of combinatorics.; Care must be taken with calculations to avoid integer overflow, although the iterative approach with `long` helps mitigate this.
### Explanation
To get from `(0, 0)` to `(m-1, n-1)`, the robot must make a total of `(m-1)` moves down and `(n-1)` moves right.

The total number of moves is `N = (m-1) + (n-1) = m + n - 2`.

We need to choose `K = (m-1)` positions for the 'down' moves out of the `N` total moves (the rest will automatically be 'right' moves). This is a classic combination problem, and the number of ways is given by the binomial coefficient "N choose K", denoted as `C(N, K)`.

The formula is `C(N, K) = N! / (K! * (N-K)!)`.

In our case, `N = m + n - 2` and `K = m - 1`. So the answer is `C(m + n - 2, m - 1)`. Calculating factorials directly can lead to overflow. A better way is to compute the result iteratively using the property `C(N, K) = (N * (N-1) * ... * (N-K+1)) / K!`.

```java
public class Solution {
    public int uniquePaths(int m, int n) {
        // Total moves = (m-1) + (n-1) = m + n - 2
        // We need to choose (m-1) down moves or (n-1) right moves.
        // This is C(m+n-2, m-1) or C(m+n-2, n-1)
        int N = m + n - 2;
        int k = m - 1; // or n - 1
        
        long res = 1;
        // Calculate C(N, k) = (N * (N-1) * ... * (N-k+1)) / k!
        // To avoid large intermediate numbers, we do multiplication and division in each step.
        for (int i = 1; i <= k; i++) {
            res = res * (N - i + 1) / i;
        }
        return (int) res;
    }
}
```
### Algorithm
- `1. Calculate total moves `N = m + n - 2`.`
- `2. Calculate moves of one type, say `k = m - 1`.`
- `3. To optimize, choose the smaller of `k` and `N-k`. Let `k = min(m-1, n-1)`.`
- `4. Initialize `result = 1` (using a long to prevent overflow).`
- `5. Loop from `i = 1` to `k`. In each iteration, update `result = result * (N - i + 1) / i`.`
- `6. Return the final `result` cast to an integer.`

# Solutions
### Java

```java
class Solution {
public
  int uniquePaths(int m, int n) {
    int[] f = new int[n];
    Arrays.fill(f, 1);
    for (int i = 1; i < m; ++i) {
      for (int j = 1; j < n; ++j) {
        f[j] += f[j - 1];
      }
    }
    return f[n - 1];
  }
}

```

### JavaScript

```javascript
/** * @param {number} m * @param {number} n * @return {number} */ var uniquePaths =
  function (m, n) {
    const f = Array(n).fill(1);
    for (let i = 1; i < m; ++i) {
      for (let j = 1; j < n; ++j) {
        f[j] += f[j - 1];
      }
    }
    return f[n - 1];
  };

```

### CPP

```cpp
class Solution {
public:
  int uniquePaths(int m, int n) {
    vector<int> f(n, 1);
    for (int i = 1; i < m; ++i) {
      for (int j = 1; j < n; ++j) {
        f[j] += f[j - 1];
      }
    }
    return f[n - 1];
  }
};

```

### Python

```python
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:  # avoid setting dp[][] to 1 for i==0 or j==0 as initialization dp = [[ 1 ] * n for _ in range ( m )] for i in range ( 1 , m ): for j in range ( 1 , n ): dp [ i ][ j ] = dp [ i - 1 ][ j ] + dp [ i ][ j - 1 ] return dp [ - 1 ][ - 1 ]

```