Reaching the Summit: How to solve Climbing Stairs algorithm question in JavaScript
Step-by-step walkthrough on how to solve the Climbing Stairs (#70 on Leetcode) in JavaScript in an efficient manner
Hello Friends, it has been too long.
I hope everyone is doing well & staying safe in this crazy world. Life happens quickly — since I’ve written my last blog post, I find myself living in a new studio apartment, missing some key pieces of furniture as they were stolen during my move, and also finally receiving a full-time paycheck from a company.
Life is full of surprises, good & bad. But I suppose that’s why we get up each morning, to expect the unexpected, and to keep striving to reach the summit of whatever we’re trying to reach on a journey that is called Life.
As I sit at my desk this morning, I can’t help but count my blessings. After a grueling 8 month job search (and approximately 1.5 years since I received a full-time paycheck), I can finally say that a company decided to take a chance on me. The timing couldn’t have been more perfect — I was reaching the last months of my lease agreement with uncertainty looming. Securing this offer allowed me to finally found a place on my own, and I couldn’t be more happier.
However, not all is perfect. While this past year I have discovered my passion for coding, I find myself in a position where I’m not actively coding everyday. In fact, I’m working with a no-code platform, which may be the case for months, perhaps years, to come.
I decided to take a crack at my old best friend, Leetcode, to keep my skills sharp…and let’s just say our reunion wasn’t all that friendly.
Here’s my walkthrough on how I (and a friend) solved this challenging, yet fittingly named, problem called Climbing Stairs.
*If you’d like to jump directly to my most efficient solution, scroll down to the heading called The Solution
The Problem
This algorithm can be found on Leetcode using the following link. I recommend you to code along if you’re having difficulty:
“You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?”
The problem sounds simple enough right? Well, let’s take a look at the example test cases that Leetcode provides:
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 stepsOK that looks simple enough. If n = 2, we can easily determine that there are two ways for us to take these two steps — we can go slow & steady and take one step at a time, or we can feel adventurous, skip a step, and take two steps.
Let’s take a look at the next test case:
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 stepThis one is a little trickier but still pretty straightforward. Based on simple logic, we can quickly determine that there are three different ways we can reach the top of a 3 step staircase — we can go slow & steady, take our adventurous leap right off the bat, or save it for after we take our first step.
Not bad so far right? But what if n=12, or n=45? Unless you’re a logic guru, it’ll take us a while to write down all of the different possibilities.
I was stumped & didn’t know what to do next. But then my friend suggested that we continue with n=4 & n=5 and see if we notice any patterns. And that’s when we had our light bulb moment.
The Approach
As stated above, let’s take the old school approach and see what happens. We’ve already done n=2 & n=3. I’ll list the results here:
2: [2]
- 1, 1
- 2
3: [3]
- 1, 1, 1
- 2, 1
- 1, 2
Makes sense so far right? There are two different approaches for n=2 and 3 different approaches for n=3. Let’s do n=4, n=5, n=6 and see what happens:
4: [5]
- 1, 1, 1, 1
- 2, 2
- 1, 1, 2
- 2, 1, 1
- 1, 2, 1
5: [8]
- 1, 1, 1, 1, 1
- 2, 2, 1
- 1, 2, 2
- 2, 1, 2
- 1, 1, 2, 1
- 2, 1, 1, 1
- 1, 2, 1, 1
- 1, 1, 1, 2
6: [13]
- 1, 1, 1, 1, 1, 1
- 2, 2, 2
-1, 1, 2, 2
-1, 2, 1, 2
-1, 2, 2, 1
-2, 2, 1, 1
-2, 1, 2, 1
-2, 1, 1, 2
-1, 1, 1, 1, 2
-1, 1, 1, 2, 1
-1, 1, 2, 1, 1
-1, 2, 1, 1, 1
-2, 1, 1, 1, 1
Whew, that was a lot of steps — are your legs starting to feel sore? :)
Let’s take a break from climbing stairs and see what we have so far:
2: [2]
3: [3]
4: [5]
5: [8]
6: [13]
Notice a pattern? It may not come immediately to you, but if you look at the number of results closely, you’ll see that the two previous numbers add up to the next number! 2+3=5, 3+5=8, 5+8=13
So how do we write this in code? We can solve this recursively using the following equation:
f(n) -> f(n-2) + f(n-1)
Let’s use 4 as an example and see how that would look:
f(4)
f(4–2) + f(4–1)
f(2) + f(3)
f(2) + f(3–2) + f(3–1)
f(2) + (f(1) + f(2))
If you do the math, you’ll see that it adds up to 5, which is the total number of approaches for 4 steps!
That should be our answer right? We know that if n=1 or n=2 we can skip this recursive approach as the number of approaches equals to the number itself, so our solution might look something like this:
But hold on, when I click Submit, we get the following error:
31/45 test cases passed. Time limit exceeded
We technically have our solution, but why are we getting this error? If you think about it more carefully, when n gets to a certain point, our current solution is extremely inefficient as it runs recursively every single time, even if we’ve seen that same n before.
So how do we solve this? One approach we can take is to store our results in a memo, or object, so we can save our solution a lot of time.
The Solution
Let’s first create our memo object. Rather than just an empty object, we can immediately set our first two key:value pairs for 1 & 2 (as we already know that the values for each will equal itself). It’s also important that we set the memo outside of our function — the reason being is because if we put it inside of our function, each time our function is being called recursively, it’ll overwrite the object we had before!
As we’ll be checking our memo each iteration, we next need to check whether the key already exists in the memo. Remember, the point of this approach is to increase our efficiency. If we’ve already added the value for a certain n, we don’t need to do it again and rather just pull the value from the object.
For example, if n=5, our first iteration will check whether memo[5] exists in our object, which it does not.
We then return to our previous logic:
f(n) -> f(n-2) + f(n-1)
Only this time, we save our values inside our memo. This way, with each subsequent iteration, we’ll check if memo[n] exists.
We continue to do this recursively until we’ve added all of the keys & values needed.
Our final code will look something like this:
Conclusion
What seemed like a pretty straightforward problem turned out to be anything but. However, my biggest takeaway from this was that even though the answer wasn’t so clear in the beginning, we can work towards it by recognizing any patterns that might exist by attempting a few more test cases. The answer might not be as faraway as you think!
I hope this walkthrough helped you gained a better understanding of this problem. As for me, I think I would rather just take the stairs instead of trying something similar again.
Until next time, and don’t forget to keep climbing for the summit.
