# LeetCode — Unique Paths

### Problem statement

A robot is located at the top-left corner of a **m x n** grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Problem statement taken from: [https://leetcode.com/problems/unique-paths](https://leetcode.com/problems/unique-paths)

**Example 1:**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1638200600248/LyjQD2Mc-.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
```

**Example 3:**

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

**Example 4:**

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

**Constraints:**

```
- 1 <= m, n <= 100  
- It's guaranteed that the answer will be less than or equal to 2 * 10^9
```

### Explanation

#### Brute force approach

As per the problem statement the robot can move either down or right. We can use recursion to find the count. Let *numberOfPaths(m, n)* represent the counts of path to reach row number m and column number n in the grid. *numberOfPaths(m, n)* in C++ can be recursively written as following.

```
int numberOfPaths(int m, int n){  
    if (m == 1 || n == 1)  
        return 1;  
  
    return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);  
}
```

The time complexity of the above solution is **exponential**. There are many overlapping sub-problems and hence we can use dynamic programming approach to avoid re-computing overlapping sub-problems.

#### Dynamic programming approach

We can avoid re-computing the overlapping sub-problems by constructing a temporary 2D array count\[\]\[\] in bottom up manner using the above recursive approach.

```
int numberOfPaths(int m, int n){  
    // create a 2D array to store results of sub-problems  
    int count[m][n];  
  
    // count of paths to reach any cell in first column is 1  
    for (int i = 0; i < m; i++)  
        count[i][0] = 1;  
  
    // count of paths to reach any cell in first row is 1  
    for (int j = 0; j < n; j++)  
        count[0][j] = 1;  
  
    for (int i = 1; i < m; i++) {  
        for (int j = 1; j < n; j++)  
            count[i][j] = count[i - 1][j] + count[i][j - 1];  
    }  
  
    return count[m - 1][n - 1];  
}
```

The time complexity of the above program is **O(mn)**. The space complexity is **O(mn)**. We can reduce the space more by **O(n)** where n is column size.

#### Combinatorics approach

We have to calculate *m+n-2 C n-1* here which will be **(m+n-2)! / (n-1)! (m-1)!**

Let’s check the algorithm on how to compute the above formula:

```
- set paths = 1  
  
- loop for i = n; i < m + n - 1; i++  
  - set paths = paths * i  
  - update paths = paths / (i - n + 1)  
  
- return paths
```

**C++ solution**

```
class Solution {  
public:  
    int uniquePaths(int m, int n) {  
        long int paths = 1;  
  
        for(int i = n; i < m + n - 1; i++){  
            paths *= i;  
            paths /= (i - n + 1);  
        }  
  
        return int(paths);  
    }  
};
```

**Golang solution**

```
func uniquePaths(m int, n int) int {  
    paths := 1  
  
    for i := n; i < m + n - 1; i++{  
        paths *= i  
        paths /= (i - n + 1)  
    }  
  
    return paths  
}
```

**Javascript solution**

```
var uniquePaths = function(m, n) {  
    let paths = 1;  
  
    for(let i = n; i < m + n - 1; i++){  
        paths *= i;  
        paths /= (i - n + 1);  
    }  
  
    return paths;  
};
```

Let’s dry-run our algorithm to see how the solution works.

```
Input: m = 3, n = 7  
  
Step 1: set paths = 1  
  
Step 2: loop for i = n; i < m + n - 1  
         i = 7  
         7 < 7 + 3 - 1  
         7 < 9  
         7 < 9  
         true  
  
         paths = paths * i  
         paths = 1 * 7  
               = 7  
  
         paths = paths / (i - n + 1)  
               = 7 / (7 - 7 + 1)  
               = 7 / 1  
               = 7  
  
         i++  
         i = 8  
  
Step 3: loop for i < m + n - 1  
        8 < 8 + 3 - 1  
        8 < 9  
        8 < 9  
        true  
  
        paths = paths * i  
        paths = 7 * 8  
              = 56  
  
        paths = paths / (i - n + 1)  
              = 56 / (8 - 7 + 1)  
              = 56 / 2  
              = 28  
  
        i++  
        i = 9  
  
Step 4: loop for i < m + n - 1  
        9 < 8 + 3 - 1  
        9 < 9  
        false  
  
Step 5: return paths  
  
So we return answer as 28.
```