# Unique Paths

There is a robot on a `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:**

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

# Approach

Let us consider 2 cases initially. What if :

- We have only one row: If we have only one row and n number of columns, there will be only one unique path.
- We have only one column: Same case as above, even if we have m number of rows, there will be only one unique path.
- For all other cases, we have 2 scenarios, we can move toward the right or the bottom. In short, we have 2 choices at any given point (i, j). Move (i+1, j) towards down, or move (i, j+1) towards the right.

This leads to the initial idea of recursion. We have the choices, make any choice, and calculate the unique paths.

From the recursion tree, we can see that there can be repeating sequences that we calculate again and this can be avoided by storing the result and reuse.

This gives us a hint to memorize the previous result and reuse it whenever we find the same pattern.

# Code

## Recursive Solution — Time Limit Exceeded

`class Solution {`

public int uniquePaths(int m, int n) {

return findUniquePaths(0, 0, m, n);

}

private int findUniquePaths(int currentRow, int currentCol, int row, int col) {

if (currentRow == row - 1 && currentCol == col - 1) {

return 1;

}

if (currentRow > row || currentCol > col) {

return 0;

}

return findUniquePaths(currentRow + 1, currentCol, row, col) + findUniquePaths(currentRow, currentCol + 1, row, col);

}

}

## Recursive Solution With Memoization

`class Solution {`

public int uniquePaths(int m, int n) {

if (m == 0 || n == 0) {

return 0;

}

int [][] possibleRoutes = new int [m][n];

for (int [] routes : possibleRoutes) {

Arrays.fill(routes, -1);

}

return findUniquePaths(0, 0, m, n, possibleRoutes);

}

private int findUniquePaths(int currentRow, int currentCol, int row, int col, int [][] possibleRoutes) {

if (currentRow == row - 1 && currentCol == col - 1) {

return 1;

}

if (currentRow >= row || currentCol >= col) {

return 0;

}

if (possibleRoutes[currentRow][currentCol] != -1) {

return possibleRoutes[currentRow][currentCol];

}

int moveRight = findUniquePaths(currentRow, currentCol + 1, row, col, possibleRoutes);

int moveDown = findUniquePaths(currentRow + 1, currentCol, row, col, possibleRoutes);

return possibleRoutes[currentRow][currentCol] = moveRight + moveDown;

}

}

## Iterative Solution

`class Solution {`

public int uniquePaths(int m, int n) {

if (m == 0 || n == 0) {

return 0;

}

int [][] possibleRoutes = new int [m][n];

// if we have only a single column, then there is only a single route

for (int i = 0; i < m; i++) {

possibleRoutes[i][0] = 1;

}

// if we have only a single row, then also there is only a single route

for (int i = 0; i < n; i++) {

possibleRoutes[0][i] = 1;

}

for (int i = 1; i < m; i++) {

for (int j = 1; j < n; j++) {

// to reach dp[i][j], we can use same paths thet we used to get to dp[i - 1][j]

// dp[i][j - 1]

possibleRoutes[i][j] += possibleRoutes[i - 1][j] + possibleRoutes[i][j - 1];

}

}

return possibleRoutes[m - 1][n - 1];

}

}

# Time and Space Complexity

In recursive and iterative solutions, we traverse the matrix of size row x col. So the time complexity is O(row x col).

Extra space is used for storing the previous result. Space complexity is O(row * col)