# LeetCode Problem 62: Unique Paths

## Introduction #

- We are given a robot that trying to move from the
**top-left**corner to the**bottom-right**corner of a grid. - Number of rows
`m`

and number of columns`n`

are given. - The robot is initially located at the
**top-left**corner let’s say position`(m, n)`

of a`m x n`

grid. - The robot is trying to reach the
**bottom-right**corner of the grid`(1, 1)`

. - The robot can only move either
**down**or**right**at any point in time.

## Visualization of the Problem #

At any point in time, the robot can only move either **down** or **right**.
Let’s say the robot is located at position `(3,2)`

of a `3 x 2`

grid.

- Moving
**right**for example means moving from`(3,2)`

to`(3,1)`

. - Moving
**down**for example means moving from`(3,2)`

to`(2,2)`

.

Full tree of possible paths from `(3,2)`

to `(1,1)`

is shown below.

**Down**–>**Down**–>**Right****Down**–>**Right**–>**Down****Right**–>**Down**–>**Down**

We can generalize this recursive tree as shown below.

## Top-Down Recursive Approach #

#### Base Cases #

when the robot reaches the end `(1,1)`

or when the robot is out of bound either `x`

or `y`

is `0`

.

```
if x == 1 && y == 1 { // base case: reached the end at (1,1)
return 1
}
if x == 0 || y == 0 { // base case: out of bound
return 0
}
```

#### Recursive Calls #

- The robot can move either
**down**or**right**. - We can recursively call the function with
`x-1`

and`y`

to move**down**. - We can recursively call the function with
`x`

and`y-1`

to move**right**.

```
return fn(x-1, y) + fn(x, y-1) // recursive call: move down or move right
```

#### Putting it all together #

```
func uniquePaths(m int, n int) int {
var fn func(int, int) int
fn = func(x int, y int) int {
if x == 1 && y == 1 { // base case: reached the end
return 1
}
if x == 0 || y == 0 { // base case: out of bound
return 0
}
return fn(x-1, y) + fn(x, y-1) // recursive call: move down or move right
}
return fn(m, n)
}
```

#### Complexity Analysis #

The time complexity of the above solution is `O(2^(m+n))`

because at each step we have two choices to make either move **down** or move **right**. The space complexity is `O(m+n)`

because of the recursive calls.

## Top-Down Recursive Approach with Memoization #

#### Idea #

We can use a map to store the results of the subproblems to avoid recomputation.
The key of the map is the current position `(x, y)`

of the robot.
The value of the map is the number of unique paths from `(x, y)`

to `(1, 1)`

.
We need to add the base cases to the memoization function.

```
func uniquePaths(m int, n int) int {
type key struct {
x int
y int
}
memo := map[key]int{}
var fn func(int, int) int
fn = func(x int, y int) int {
if val, ok := memo[key{x, y}]; ok {
return val
}
if x == 1 && y == 1 { // base case: reached the end
return 1
}
if x == 0 || y == 0 { // base case: out of bound
return 0
}
ret := fn(x-1, y) + fn(x, y-1) // recursive call: move down or move right
memo[key{x, y}] = ret
return ret
}
return fn(m, n)
}
```

#### Complexity Analysis #

The time complexity of the above solution is `O(m*n)`

because we are storing the results of the subproblems in the map. The space complexity is `O(m*n)`

because of the recursive calls.

## Buttom-Up Approach with Tabulation #

#### Idea #

We can use a matrix to store the result of a subproblem for each position `(x, y)`

of the robot.

#### Base Cases #

- When the robot is at the end
`(1,1)`

the number of unique paths is`1`

. - When the robot is out of bound either
`x`

or`y`

is`0`

the number of unique paths is`0`

.

#### Iterating the Matrix #

- We will iterate the matrix from
`(1,1)`

to`(m,n)`

. - At each position
`(i,j)`

of the matrix, the number of unique paths is the sum of the number of unique paths from`(i-1,j)`

and`(i,j-1)`

.

#### Drawing the Matrix #

#### Putting it all together #

```
func uniquePaths(m int, n int) int {
matrix := make([][]int, m+1)
for i := 0; i <= m; i++ {
matrix[i] = make([]int, n+1) // initialize the matrix with array of n+1 elements
}
matrix[1][1] = 1 // base case when the robot is at the end (1,1)
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if i == 1 && j == 1 { // skip the base case
continue
}
matrix[i][j] = matrix[i-1][j] + matrix[i][j-1]
}
}
return matrix[m][n]
}
```

#### Complexity Analysis #

The time complexity of the above solution is `O(m*n)`

because we are iterating the matrix from `(1,1)`

to `(m,n)`

. The space complexity is `O(m*n)`

because of the matrix.

## Buttom-Up Approach with Tabulation (Memory Optimized) #

#### Idea #

We can use a 1D array to store the result of a subproblem for each position `(x, y)`

of the robot.
Since we only need the result of the previous row to calculate the result of the current row, we can use a 1D array to store the result of the previous row.

#### Code #

```
func uniquePaths(m int, n int) int {
arr := make([]int, n)
for i := range arr {
arr[i] = 1
}
for i := 0; i < m-1; i++ {
for j := len(arr) - 2; j >= 0; j-- { // iterate the array from right to left
arr[j] = arr[j] + arr[j+1]
}
}
return arr[0]
}
```

#### Complexity Analysis #

The time complexity of the above solution is `O(m*n)`

because we are iterating the matrix from `(1,1)`

to `(m,n)`

. The space complexity is `O(n)`

because of the 1D array.