Solving Leetcode 70 - Climbing Stairs (JavaScript) (Fibonacci sequence)

It's been a lot of fun completing one algorithm problem a day! I feel there is plenty time to go but I firmly believe given enough variety (and time) I will better master critical concepts. We previous have worked on two sum and atoi() which involve some clever tricks and helper methods that JavaScript provides. Today we are going to talk about something a little different and start dipping our toes into the concept of recursion and iterative solutions with leetcode 70 climbing stairs.

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps.

In how many distinct ways can you climb to the top?

Seems simple enough at first glance. Essentially we just want to count how many ways we can take n amount of steps when given the option taking stairs one or two at a time. Something that isn't explicitely called out here is that all permutations are valid (ie in the case of needing to take 3 steps, 1+2 and 2+1 are distinct values and both count). But otherwise we should be able to write a function that can solve this question for any arbitrary amount of steps n.

Approach 1 - Tried and true Fibonacci sequence

Do not panic. You aren't in a nightmare where you are back in math class and you forgot to study for the test. We aren't going to go too deep into what fibonacci sequence is today (likely in a later blogpost) but effectively its a sequence of numbers where the each number is effectively the sum of the two previous values in the sequence. Confused? That's okay. Let's take a look at an example sequence (n=0 has a value of 1):

| N | Value | Previous two values | | :-: | :---: | :-----------------: | | 0 | 1 | n/a | | 1 | 1 | 1 + n/a | | 2 | 2 | 1 + 1 | | 3 | 3 | 1 + 2 | | 4 | 5 | 2 + 3 | | 5 | 8 | 3 + 5 | | 8 | 13 | 5 + 8 |

So what pattern do you observe? As previous states each numbers (with the exception of 0 and 1 which are somewhat of special cases) for a given N it is indeed the value of the sum of the previous values N-1 and N-2. You don't have to be an expert in fibonacci after this but keep this in mind.

So what the heck did all of that have to do with climbing steps? Well it turns out we have a very similar pattern. Now let's generate a new table based on a few steps taken climbing stairs:

| Stairs Climbed | Combinations of steps | Total combinations | | :------------: | :---------------------------------: | :----------------: | | 0 | 1 | 1 | | 1 | 1 | 1 | | 2 | [1+1, 2] | 2 | | 3 | [1+1+1 ,2+1, 1+2] | 3 | | 4 | [1+1+1+1, 1+1+2, 2+1+1, 1+2+1, 2+2] | 5 |

Do you see something similar here? If not thats okay. Let me add another column and see if that helps:

| Stairs Climbed | Combinations of steps | Total combinations | Previous two combinations | | :------------: | :---------------------------------: | :----------------: | :-----------------------: | | 0 | 1 | 1 | n/a | | 1 | 1 | 1 | n/a | | 2 | [1+1, 2] | 2 | 1+1 | | 3 | [1+1+1 ,2+1, 1+2] | 3 | 2+1 | | 4 | [1+1+1+1, 1+1+2, 2+1+1, 1+2+1, 2+2] | 5 | 2+3 |

What we see is that the quanity of of the previous two combination for a given step (for example 3 steps yields 3 combinations to make it to the third step) is simply the sum of the previous two step combinations (combinations for taking one step and combinations for two steps). That's right you've been had. This problem is actually fibonacci sequence 🤯

Alright now that the cat 🐱 is out of the bag how can we use this to solve our problem? Well in the world of programming we have a powerful tool called recursion. Recursion itself commands a separate blog post but essentially think of recursion like a method that calls itself over and over until it gets some final answer. The basic concept is pretty simple but it's really easy to get in trouble quick (the classic site name Stack Overflow is a pretty classic example of what happens when recursion goes wrong.) But for another time.

Implementation

A classic implementation of fibonacci recursion is as below:

const climbStairs = (n) => {
  //base case
  if (n <= 1) return 1;

  //otherwise this is basically fib sequence f(n) = f(n-1) + f(n-2)
  return climbStairs(n - 1) + climbStairs(n - 2);
};

Looks deceptively simple no? But it's actually simple in this case once you understand the trick. The first line of code is called our base case. This is is essentially what prevents the dreaded stack overflow and allows our function to always bail out with a final answer. After all returning a number is quite finite and shouldn't cause to many issues.

The real magic occurs in the second line. We return from the function by returning the sum of two calls of the fibonacci sequence, one at one less than the number of steps we are checking for and another two less than the steps we are checking for. HUH? Well it's still not too bad. We can start to talk about the call stack here but I think that is a little too imperative. Rather I want to describe in english what is going on.

Every time climbStairs() is called we going to now have two copies of that function in memory. Those two copies of the function are then going to spawn up to another two copies of the function. This "doubling" will keep happening until these copies hit n <= 1. Makes sense? No? Lets look at a table for n = 3:

| Count | calls | | :---: | :------------------------------------------: | | 0 | climbStairs(3) | | 1 | climbStairs(2),climbStairs(1) | | 2 | climbStairs(1),climbStairs(0),climbStairs(0) |

So after 3 recursive calls you can see we actually distilled down to 3 calls of n=1,0,0. Now why did we stop here? Recall our base case:

//base case
if (n <= 1) return 1;

We said when n is 1 or 0 in the function returns the value of 1. And in line two of our method we are summing calls. So if we replace the methods in count two of our stack we get:

// 1 + 1 + 1 = 3

Which gasp is exactly the value we expect from a few tables ago. So we have a very small method that is able to calculate the fib sequence. We are done right? Do me a favor. Try to plugin N = 37. 🙃 I'll be here waiting (spoiler: You will be waiting a long time).

O(n) Cost

Now. There must have been some reason I pointed out n = 37 is a problem for this method. It turns out while this implemented is efficient in terms of lines of code, it is terrible performance wise for moderately sized N. There is a general rule of thumb to estimate O(n) for recursion scenarios. Without telling you the answer lets look above again at my calls table. You don't quite see what's happen but the number of calls is increasing. In fact it increases at a rate of doubling because recall I am summing n-1 and n-2 result. We can represent this as O(2^N).

Just how terrible is this? Well 2^37 is 137438953472 calls. Yeah.... that's a lot. And it turns out even with a moderately fast computer that's going to take some time. So is there something better we can do?! Of course there is!

Approach 2 - Iterative solution with memoization

There is actually a pretty clever little trick we can use to create a method that significantly outperforms vanilla recursive fibonacci. To arrive at this solution first ask yourself What the heck is being calculated in each of those iterations? Time to reference our previous table:

| Count | calls | | :---: | :------------------------------------------: | | 0 | climbStairs(3) | | 1 | climbStairs(2),climbStairs(1) | | 2 | climbStairs(1),climbStairs(0),climbStairs(0) |

What do we see in this table that is common? Well we see that climbStairs is called with n = 0 and n = 1 twice. Now imagine the duplication as N increases. Does the value of climbStairs for a given n in the call stack change? No it doesn't does it? So for example climbStairs(3) will always evaluate to 5 no matter how many times you calculate it. And this is the problem with classic fibonacci implemnentation at larger N values We constantly repeat calculations and do so A LOT. 😢

So if we already know the answer to a given call to climbStairs why not use it again? Turns out we can do so using our tried and true hash table previously utilized in LeetCode 1 - Two Sum.

Implementation

In english what we are going to do is replace the recursive call with an iterative loop instead. And inside the iterative loop we are going to generate a new hash value for a given n (starting at 2) all the way up to the desired number of steps (n).

const cache = {
  0: 1,
  1: 1,
};

const climbStairs = function (n) {
  //base cases
  if (n <= 1) return 1;
  for (let i = 2; i <= n; i++) {
    cache[i] = cache[i - 1] + cache[i - 2];
  }
  return cache[n];
};

So effectively what is happening here is each step in the loop we generate the new value in the cache using the two previous values we have inside our cache object. So cache(2) = cache(1) + cache(0) = 2 which then gets stored as a key/value pair. There is no redundant recalculating of all the sub recursive cases as in approach one. We instead direct use the previously calculated answer. Then once we have reached the end of the loop we return the final answer.

O(n) Cost

So how much better is this? Normally loops are frowned upon because unless we apply the concept of divide and conquerer (another post in the near future) we immediately must assume we have to iterate at least the length of the loop. And that in fact holds true. But what is the cost of looking up a value in a hash table if each key has one value? O(1). So taking that into consideration and dropping this for a sufficiently large N it turns out our cost with this method is O(n).

Side note

You can actually apply memoization to implementation 1 and get a similar runtime to method two. I will leave this exercise to you the reader to implement! The intention is to show that an iterative solution is not necessarily inferior to a recursive solution. Rather one must understand the requirements of the problem when determining the best approach to take. 😃

Conclusion

I hope you come from this post with a basic understanding of fibonacci sequence, recursion and iterative solutions. I will be solving plenty of additional problems over the next few weeks in the same vein so hopefully we can continue to learn together. Thank you and best of luck solving algorithms!