# Unique Paths Problem

A robot is located at the top-left corner of a m x n grid. 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. How many possible unique paths are there?

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?

**Example #1**

```
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 -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
```

**Example #2**

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

## Backtracking

First thought that might came to mind is that we need to build a decision tree
where `D`

means moving down and `R`

means moving right. For example in case
of boars `width = 3`

and `height = 2`

we will have the following decision tree:

```
START
/ \
D R
/ / \
R D R
/ / \
R R D
END END END
```

We can see three unique branches here that is the answer to our problem.

**Time Complexity**: `O(2 ^ n)`

- roughly in worst case with square board
of size `n`

.

**Auxiliary Space Complexity**: `O(m + n)`

- since we need to store current path with
positions.

```
/**
* BACKTRACKING approach of solving Unique Paths problem.
*
* @param {number} width - Width of the board.
* @param {number} height - Height of the board.
* @param {number[][]} steps - The steps that have been already made.
* @param {number} uniqueSteps - Total number of unique steps.
* @return {number} - Number of unique paths.
*/
export default function btUniquePaths(
width,
height,
steps = [[0, 0]],
uniqueSteps = 0
) {
// Fetch current position on board.
const currentPos = steps[steps.length - 1]
// Check if we've reached the end.
if (currentPos[0] === width - 1 && currentPos[1] === height - 1) {
// In case if we've reached the end let's increase total
// number of unique steps.
return uniqueSteps + 1
}
// Let's calculate how many unique path we will have
// by going right and by going down.
let rightUniqueSteps = 0
let downUniqueSteps = 0
// Do right step if possible.
if (currentPos[0] < width - 1) {
steps.push([currentPos[0] + 1, currentPos[1]])
// Calculate how many unique paths we'll get by moving right.
rightUniqueSteps = btUniquePaths(width, height, steps, uniqueSteps)
// BACKTRACK and try another move.
steps.pop()
}
// Do down step if possible.
if (currentPos[1] < height - 1) {
steps.push([currentPos[0], currentPos[1] + 1])
// Calculate how many unique paths we'll get by moving down.
downUniqueSteps = btUniquePaths(width, height, steps, uniqueSteps)
// BACKTRACK and try another move.
steps.pop()
}
// Total amount of unique steps will be equal to total amount of
// unique steps by going right plus total amount of unique steps
// by going down.
return rightUniqueSteps + downUniqueSteps
}
```

## Dynamic Programming

Let's treat `BOARD[i][j]`

as our sub-problem.

Since we have restriction of moving only to the right and down we might say that number of unique paths to the current cell is a sum of numbers of unique paths to the cell above the current one and to the cell to the left of current one.

```
BOARD[i][j] = BOARD[i - 1][j] + BOARD[i][j - 1]; // since we can only move down or right.
```

Base cases are:

```
BOARD[0][any] = 1; // only one way to reach any top slot.
BOARD[any][0] = 1; // only one way to reach any slot in the leftmost column.
```

For the board `3 x 2`

our dynamic programming matrix will look like:

0 | 1 | 1 | |
---|---|---|---|

0 |
0 | 1 | 1 |

1 |
1 | 2 | 3 |

Each cell contains the number of unique paths to it. We need
the bottom right one with number `3`

.

**Time Complexity**: `O(m * n)`

- since we're going through each cell of the DP matrix.

**Auxiliary Space Complexity**: `O(m * n)`

- since we need to have DP matrix.

```
/**
* DYNAMIC PROGRAMMING approach of solving Unique Paths problem.
*
* @param {number} width - Width of the board.
* @param {number} height - Height of the board.
* @return {number} - Number of unique paths.
*/
export default function dpUniquePaths(width, height) {
// Init board.
const board = Array(height)
.fill(null)
.map(() => {
return Array(width).fill(0)
})
// Base case.
// There is only one way of getting to board[0][any] and
// there is also only one way of getting to board[any][0].
// This is because we have a restriction of moving right
// and down only.
for (let rowIndex = 0; rowIndex < height; rowIndex += 1) {
for (let columnIndex = 0; columnIndex < width; columnIndex += 1) {
if (rowIndex === 0 || columnIndex === 0) {
board[rowIndex][columnIndex] = 1
}
}
}
// Now, since we have this restriction of moving only to the right
// and down we might say that number of unique paths to the current
// cell is a sum of numbers of unique paths to the cell above the
// current one and to the cell to the left of current one.
for (let rowIndex = 1; rowIndex < height; rowIndex += 1) {
for (let columnIndex = 1; columnIndex < width; columnIndex += 1) {
const uniquesFromTop = board[rowIndex - 1][columnIndex]
const uniquesFromLeft = board[rowIndex][columnIndex - 1]
board[rowIndex][columnIndex] = uniquesFromTop + uniquesFromLeft
}
}
return board[height - 1][width - 1]
}
```

## Pascal's Triangle Based

This question is actually another form of Pascal Triangle.

The corner of this rectangle is at `m + n - 2`

line, and
at `min(m, n) - 1`

position of the Pascal's Triangle.

```
/**
* @param {number} lineNumber - zero based.
* @return {number[]}
*/
function pascalTriangle(lineNumber) {
const currentLine = [1]
const currentLineSize = lineNumber + 1
for (let numIndex = 1; numIndex < currentLineSize; numIndex += 1) {
// See explanation of this formula in README.
currentLine[numIndex] =
(currentLine[numIndex - 1] * (lineNumber - numIndex + 1)) / numIndex
}
return currentLine
}
/**
* @param {number} width
* @param {number} height
* @return {number}
*/
export default function uniquePaths(width, height) {
const pascalLine = width + height - 2
const pascalLinePosition = Math.min(width, height) - 1
return pascalTriangle(pascalLine)[pascalLinePosition]
}
```

Same series: