Photo by Mitchell Luo on Unsplash

# How to Solve the Unique Paths Leetcode Problem with JavaScript and Recursion

## Beginner Friendly Step-by-Step Walkthrough to a Notorious Leetcode Problem

I'm going to show you how to *conquer* a notoriously difficult leetcode problem: Unique Paths.

And in subsequent posts I will show you how to solve: Unique Paths II (Unique Paths with BARRIERS), and Unique Paths III. **So please go ahead and click +follow button on the upper right to get future updates.** ๐๐

# ๐คฏ

Don't worry if you're new to programming and have never solved a recursion problem in your life. I'll hold your hand and step you through it.

When I first learned recursion in high school CS class, I freaking hated it. ๐ Took me years to really understand it. **My goal in this post is to cut down that learning curve for you, hopefully down to just reading THIS post! **

### Why Unique Paths?

Because if you understand how to solve the Unique Paths leetcode problem, you got an excellent grasp of recursion. *Recursion is one of the most abstract and difficult concepts in computer science, IMHO. If you can get a deep understanding of how it works, you're head and shoulders ahead of the competition!*

### What the heck is Unique Path Problems Anyway?

You can read about the simplest version here. In so many words:

- You have an
`m x n`

grid, and you're starting at position`[0][0]`

- You can move only right or down
- Your goal is to get to position
`[m-1][n-1]`

, the opposite corner.

*The Problem:* count ALL the unique paths to go from `[0][0]`

to `[m-1][n-1]`

.

*Count what ?? Yea, if you've never seen this problem, it's a mind bender. *๐ค

There are a bunch of different ways to solves this problem, even with recursion. I'm going to present a solution that easy to understand...well, was for me anyhow:

```
// determine paths through grid of size m x n
// starting at [y = 0][x = 0] and
// ending at [y = m - 1][x = n - 1]
function UniquePaths(m, n, y = 0, x = 0) {
const atWallX = Boolean(x === n - 1); //at right wall of grid
const atWallY = Boolean(y === m - 1); //at bottom wall of grid
if (atWallX && atWallY) {
//CONGRATS you've hit the destination!!
// add +1 to the count of unique paths
return 1;
}
else if (atWallX && !atWallY) // can move down but not right
return UniquePaths(m, n, y + 1, x);
else if (atWallY && !atWallX) // can right but not down
return UniquePaths(m, n, y, x + 1);
else { // => (!atWallY && !atWallX) => can move right or down
return UniquePaths(m, n, y + 1, x)
+ UniquePaths(m, n, y, x + 1);
}
}
```

### Take a Deep Breath! Let's Walk through This....

#### Some Context ๐ค

We have a function `UniquePaths(m, n, y = 0, x = 0)`

that going to recursively walk us through the grid, one step at a time, from `y = 0, x = 0`

(upper left of grid) to our final destination at `y = m - 1, x = n - 1`

(lower right of grid).

There are 4 arguments to `UniquePaths(...)`

: `m`

, `n`

, `x`

, and`y`

. `m`

and `n`

are just the fixed dimensions of the grid. `x`

is a count of how many steps to the right we've taken (i.e. x coordinate). `y`

is a count of how many steps down we've taken (i.e. y coordinate).

### Big Picture

`UniquePaths(m, n, y = 0, x = 0)`

will recursively walk through the grid, checking all possible paths by incrementing the value of `x`

and `y`

by `+1`

(when possible). When a path hits `y = m -1, x = n - 1`

, it will `return 1`

, which will go towards the count of unique paths.

If this last paragraph is confusing, don't worry. *As you read the rest of this post, it will all make 100% sense.*

### Checking if We're Up Against a Wall

Next we define 2 Booleans which will tell us if we've against a wall (edge of the grid):

```
const atWallX = Boolean(x === n - 1); //at right wall of grid
const atWallY = Boolean(y === m - 1); //at bottom wall of grid
```

Remember, we can only move right or down. These 2 Booleans tells us if we CAN move right in our next step (`atWallX === false`

) or if we CAN move down in our next step (`atWallY === false`

).

Now I know some smart ass will comment on how this is unnecessary and show us how to solve this problem in 1 line of code. *Listen:* there's a specific reason I'm coding the problem this way. You'll understand what I'm talking about when we work on solving the more complex Unique Code II & III leetcode problems.

Here's a hint at what I'm getting at...

## ๐

### Time to Tango on the Grid Dance Floor

Now it's time to move either: right, down, or *both*:

```
if (atWallX && atWallY) {
//CONGRATS you've hit the destination!!
// add +1 to the count of unique paths
return 1;
}
else if (atWallX && !atWallY) // can move down but not right
return UniquePaths(m, n, y + 1, x);
else if (atWallY && !atWallX) // can right but not down
return UniquePaths(m, n, y, x + 1);
else { // => (!atWallY && !atWallX) => can move right or down
return UniquePaths(m, n, y + 1, x)
+ UniquePaths(m, n, y, x + 1);
}
```

Here's where our Booleans REALLY come in handy.

*We're going to skip the first if statement for the moment.* **Let's first discuss how we move through the grid first:**

`if (atWallX && !atWallY)`

you've moved to the right as much as you can, now you can only move down, i.e.`y => y + 1`

. We return`UniquePaths(m, n, y + 1, x)`

with our new position: one additional step down on the grid.On the other hand,

`if (atWallY && !atWallX)`

then you've moved as much down as you can, and can only move right. i.e.`x => x + 1`

. We return`UniquePaths(m, n, y, x+1)`

with our new position: one additional step right on the grid.

## The 2 Step

**The last scenario is a tricky one: ** We're NOT against a wall. We can move either right or down. Since we're counting **ALL unique paths**, we need to account for BOTH scenarios.

Luckily, we have a super power with recursion: *we can clone ourselves!*

We can step downward: `UniquePaths(m, n, y + 1, x)`

While our clone steps rightward: `UniquePaths(m, n, y, x + 1)`

To account for the total unique paths from both combinations, we add them:

```
else { // => (!atWallY && !atWallX) => can move right or down
return UniquePaths(m, n, y + 1, x)
+ UniquePaths(m, n, y, x + 1);
}
```

Guess what? Every time we break off and clone ourselves like this, we're creating a NEW unique path! And each unique path will eventually `return 1`

.

So imagine `return UniquePaths(m, n, y + 1, x) + UniquePaths(m, n, y, x + 1)`

, and let's say each of these `UniquePaths(...)`

returns another `return UniquePaths(m, n, y + 1, x) + UniquePaths(m, n, y, x + 1)`

and so on! **You keep cloning yourself, over and over!**

If we work through all the recursive calls, the final `return`

statement will look something like:

```
return UniquePaths(m, n, ...)
+ UniquePaths(m, n, ...)
+ UniquePaths(m, n, ...)
+ UniquePaths(m, n, ...)
+ UniquePaths(m, n, ...)
+ ...
```

####But when does it end? ๐ต

When we hit `UniquePaths(m, n, m - 1, n - 1)`

we're at the lower right corner (`y = m -1`

and `x = n - 1`

), finally!!

# ๐บ

Go back and look at the first if statement in the code.

**This is the exit condition for our recursive calls to UniquePaths(...)...**

```
if (atWallX && atWallY) {
//CONGRATS you've hit the destination!!
// add +1 to the count of unique paths
return 1;
}
```

Once we hit the lower right corner (`y = m -1`

and `x = n - 1`

), we `return 1`

. Each of these `UniquePaths(m, n, ...)`

will `return 1`

:

```
return UniquePaths(m, n, ...)
+ UniquePaths(m, n, ...)
+ UniquePaths(m, n, ...)
+ UniquePaths(m, n, ...)
+ UniquePaths(m, n, ...)
+ ...
```

On the final return statement, `...`

is actually just `m - 1, n - 1`

. It's going to look like this:

```
return UniquePaths(m, n, m - 1, n - 1)
+ UniquePaths(m, n, m - 1, n - 1)
+ UniquePaths(m, n, m - 1, n - 1)
+ UniquePaths(m, n, m - 1, n - 1)
+ UniquePaths(m, n, m - 1, n - 1)
+ ...
```

These are all the unique paths summed up! Each `UniquePaths(m, n, m - 1, n - 1)`

is the result of the end journey of 1 path starting out at `[0][0]`

and getting cloned every time it had the option of going right or down. Each will `return 1`

:

```
return 1
+ 1
+ 1
+ 1
+ 1
+ ...
```

And THAT sum is our **total count of unique paths**!