Climbing Stairs (LeetCode #70)

Image by Maksym Ostrozhynskyy 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 Maximum Product Subarray.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Climbing Stairs problem, you’re in the exact right place.

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.

I’m going to teach you a formula that will let you solve it immediately from here on out!

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’ll be climbing a staircase which has n steps to reach the top
2. We can either climb 1 or 2 steps at a time
3. n (the top of the steps) will be 1 <= n <= 45
4. We need to return the number of distinct ways we can climb to the top

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.

That’s good enough to kick this whole thing off. Let’s go ahead and get started!

Setup 🏗

This is actually one of the first “dynamic programming” problems that we’ve done together. These problems can seem super intimidating until you pick up some tricks to solving them.

We’ll work through it together. Sound good?

The first thing we want to do is to initialize a dictionary to use as a cache for this problem!

We’ll be using this for the rest of the problem. Now that we have a cache setup, we can get into the core concept of this problem — backtracking!

Backtracking 🐾

Backtracking is a core concept for some types of dynamic programming questions. It utilizes the concepts that:

1. Functions stack on top of each other in the call stack so that later-called functions finish before the earlier-called ones
2. Functions at the top of the stack (e.g. later-called ones) can add values to the cache that the functions called earlier (and are lower in the call stack) can then access

Essentially, backtracking means that we recursively call a function and cache the results. We’re doing what’s called a “bottoms-up approach” which means we solve the last (or “bottom”) problems first (in this case, the total ways to get from the second-to-last step to the last one, the third-to-last step to the second-to-last one, etc.).

Here’s a diagram of how we might start at step 0 and recursively call functions to climb the series of steps (+ 1 and + 2 for each step):

In the diagram above, we start at step 0 and call our backtracking function (which we’re about to write). Inside that call, we then call our backtracking function again with 0 + 1 and 0 + 2 as the new steps (since we can climb the stairs 1 or 2 steps at a time).

Each one of those function calls then does the same thing. The functions that finish first (in a depth-first fashion) will then store their result in the cache. We can then reuse these values for other function calls by checking in other functions if we have cached that step number (e.g. in the diagram above, the lefthand chain of calls will end up caching values that the righthand side will use later on).

With our backtracking function, we can also return 1 for any time we reach the final step. As the results from functions at the top of the call stack are returned, the functions in the call stack behind them can add them up and then store that as the value for that step in the cache.

Here’s what our backtracking function looks like in code:

In this function, we first check if the current_n passed in as a parameter for this function is greater than the last step. If so, it’s an invalid step up and we return 0.

Next, we check if current_n is equal to n. If so, we’ve found our valid base case for reaching the final step and we should return 1.

Finally, we check if current_n is already in the cache (from previous function calls). If it is, we should return that value to avoid recomputing (calling new functions) for work we’ve already done. This is where the real caching savings comes in.

If none of these cases are true, it means the step hasn’t been visited and cached yet. We should go ahead and set the current_n step in the cache equal to the result from:

backtrack(current_n + 1) + backtrack(current_n + 2)

This will recursively call our functions (which will themselves be setting values in the cache for future performance savings) and set whatever their combined return values are to the cache for the current_n step.

We then want to return the value of cache[current_n] that we just set.

Once all of this is done, we should go ahead and do one more thing — we need to actually call this function. Since the final returned value from it (the first function call) should be the total of all distinct ways we’ve been able to climb the steps, we can merely write:

We’re returning the result of our backtrack function starting at the 0 step.

BOOM. There’s our solution.

This will run in O(n) time complexity (since we only need to calculate the total for each step once in a bottoms-up approach and use that cached value thereafter in a constant time of O(1)) and space complexity of O(n) (since we cache the value of every step in n and also have a call stack the size of n).

Conclusion

There we go. I hope this helped you out! I know it probably stretched your mind a bit with the backtracking. It totally did for me when I started learning it.

Keep an eye out for the rest of these Blind 75 coding challenges articles. 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)