To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
Recommend this publication to Substack over here
I know you’ve been hungry for this solution.
I can hear your stomach grumbling from over here.
It’s time to eat.
This problem can be found as problem 70. Climbing Stairs on Leetcode.
Problem
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?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
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 step
Constraints:
1 <= n <= 45
You can test your solution here
I have some really interesting information for you at the end. Use that to show off in your interviews and get those bonus points.
Step 1: Looking for patterns
There are a few things about this question-
It’s simple to understand.
We can break this problem into different sub-parts. When climbing stairs, the act of climbing each individual stair is identical, whether you’re on steps 1,5, or 10. Assuming of course there are more steps left to climb at each of these points.
This points to a recursive sub-structure. We don’t know what the exact recurrence relations are at this point. We will figure them out. How do we do this?
When starting off with a question like this, I like to start playing with small test cases to see if I can spot a pattern. This is a technique that you will see me use often in this newsletter, especially with questions that involve math/recursion. To get better with this for recursion specifically, check out my post on Mathematical Induction and Recursion.
So let’s do that.
Step 2: Testing a few Sample inputs
So what does our expected output look like?
The next smallest input is 4. With n=4, we end up with a result of 5. With n=5, we will end up with 8. You can verify these for yourself if you’d like. The numbers are starting to get too big for me, so this is where I would stop and take a step back.
Okay, so where to go from here? Let’s go back to analyzing the structure of this problem.
Let’s say we’re at step n. To get here, there are only two possible steps we could have taken- (n-1) and (n-2). Regardless of how we got to these, we can only use one of these to get to n directly.
This is true for every n that is not 1 or 2 (since both of these would lead to n-1==0 and n-2==0 respectively). So these 2 become our base cases. Neat. That’s a huge step in finding our recurrence relation. Now for the main relation.
Step 3: Finding a Recurrence Relation
We already know that we can only get to step n from either step n-1 or n-2. What else can we figure out?
Let’s say that we were going through n-1. We know that no matter how we reach step n-1, there’s only one way to reach n from here. The same holds true for n-2. We don’t really care how we got to either of these stepping stones, there is only one path is forward (to reach n). And each route that we took to get to either of these stepping stones is valid.
So essentially, the way we reach n would be-
ways(n)= ways(n-1) + ways(n-2)
Fun math problem- how would this change if you could take multiple paths to get to n from n-1/n-2? Or how would it change if you added more possible steps you could take at a time? Think about it and lmk. The hint for the former problem is in last week’s solution
Okay, we have a recurrence relation and base cases. So we can get to coding? It shouldn’t be hard to implement DP on a relatively simple relation. I saw lots of solutions online just coding things up. We will do one final thing.
Step 4: Recognizing the Fibo
If you go to your interview, solve this relationship, and not are unable to recognize that this is the exact formulation for the Fibonacci series, God help you. I will find you and spray paint this function all over your house. If your mom wakes you up at 3 AM and asks you to recognize this formulation, you’d better get this right.
Here is why that is important here. One- it allows you to show off your knowledge. Two- You could mechanistically implement a Dynamic Programming solution by using a cache to store the number of ways. I saw a lot of solutions do this. But, if you know the code for generating Fibonacci numbers, you can attain the same results by using just 2 variables. You go from O(n) to O(1) space usage.
Let’s now look over the code. Because this is such an important function, make sure you really get this. On a spiritual level.
Step 5: Code (+ Fun Math Trivia)
The code looks like this. Should not surprise you. I used an additional base case because the sample outputs gave that to us. It honestly doesn’t make a huge difference if you do it the normal way.
class Solution:
def climbStairs(self, n: int) -> int:
if(n<=3):
return n
one,two=2,3 #minus_one, minus_two
for i in range(4,n+1):
two = one + two
one = two-one
return two
Now for the fun math. Did you know that for very large n values, you can approximate them using the Golden Ratio? For very large successive values of the sequence, the values have a ratio approaching the Golden Ratio. This gives us a geometric sequence. We can thus approximate n=111000000000 directly, instead of having to generate the values. Pretty neat, huh? Will do a Math Monday on that if you’re interested. Meanwhile, make sure you flex this newfound knowledge at every possible avenue. So that bringing this up is in your muscle memory, when your interviewer asks you this question.
Time Complexity- O(N).
Space Complexity- O(1)
Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.
Stay Woke. I’ll see you living the dream.
Go kill all,
Devansh <3
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75