Unique Paths (LeetCode #62)

Image by Philip Glickman on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Merge K Sorted Lists.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Unique Paths problem, you’re in the right spot.

This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.

Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.

Let’s get it started!

Understanding the Problem 🕵🏻‍️

The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see Polya’s Problem Solving Techniques):

1. We have a robot on an m x n grid
2. The robot is initially located on the top-left corner of our grid and it needs to move to the bottom-right corner
3. The robot can move either right or down at any point in time
4. We must return the total number of unique paths that the robot can take to reach the bottom-right corner
5. m and n for the grid size will each be within 1 <= n, m <= 100

I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.

Okay. I think that’s enough housekeeping items for us to get started!

Initial Problem Setup 🏗

This is yet another dynamic programming problem. I know these can be a little shifty to work with, so we’ll take it slow and I’ll explain each step.

The real key to this problem is to realize that, since the robot can either move right or down each time, we basically need to count each move right or down as a unique combination.

For instance, here’s the example image used in the LeetCode challenge:

If we were to move right from where the robot is at the start, that is one unique path so far. Simultaneously, moving down from the start is a second unique path so far. from each of those spots, moving right or down is an additional two unique paths so far.

See where I’m going with this?

What if we were to iterate over the entire grid cell by cell and, for every one, add the top cell and the previous cell to count the unique ways so far that we’ve reached the current cell?

If we did that, we’d eventually find ourselves at the finish with a total that reflects the number of unique ways we’ve moved right or down to reach that point.

Let’s set up the initial foundation of the problem, and it will make more sense as we continue.

First, let’s set up our cache:

Notice that we’re initializing the starting space with a value of 1 (key-ed in our dictionary by (0, 0)). This is because dynamic programming problems often require some base seed value that will be used as a foundation to progressively build upon. When we first move right or down, those cells will reference this (0, 0) position. All other cells will continue to build up from there.

Next, we need to set up our nested loops to traverse our m x n matrix:

Nice. We’re ready to write the core logic of our problem.

Let’s get into it! 🤘🏻

Iterate, Cache, Iterate 🔁

First, we need to initialize a variable to track the current_total_ways. We’ll add to this as we move through our logic:

Next, we’ll have a series of if statements:

1. Check if the cell above exists (since we’re moving down from it) and add it to current_total_ways if it does
2. Check if the cell to the left exists (since we’re moving right from it) and add it to current_total_ways if it does
3. Check whether or not the current cell exists in the cache (guarding against overwriting the base (0, 0) case) and create it with a value of 0 if not

Nice. The next thing we need to do is add the outcome of current_total_ways to the cache as long as it’s greater than the current cached value of the (x, y) position (if it exists):

This will allow other cells to access this value later as we iterate.

The max comparison is really just to avoid overwriting the seed value at (0, 0) when we start our loops. This allows us to avoid a bit of extra logic.

Finally, we need to return the bottom-right cell in the matrix. This will have our final answer to the problem!

Believe it or not, this is the complete solution. That wasn’t too bad, right?

This entire solution will run in O(m * n) space and time complexity as we’re using a matrix in memory and running a nested loop over the original matrix.

Conclusion

Good job. You made it. What did you think? Was it easier or harder to understand than you expected?

Keep an eye out for the rest of these Blind 75 coding challenges articles I’m doing. It’s going to be a fun ride.

Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)