8.1 Triple Step

NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊

A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

Hmm, this sounds a lot like a recursive algorithm 🤔To me the easiest way to think about it is to start backwards. Imagine that we have 5 steps and need to calculate all combinations of hops that can cover these 5 steps. We know that the child can hop either one step, 2 steps, or 3 steps at once - which means that she got to step 5 from either from step 4, or step 3, or step 2. In other words, if n equals 5, then the number of different ways to get to n is a number of ways to get to (n-1) + ways to get to (n-2) + ways to get to (n-3). Let's call the function that would calculate the number of all possible ways to get to step x getStaircaseCombinations(x).

But how did the child get to step 4 (the n-1 from above)? She must have been either on step 3, step 2, or step 1 before, and you can observe the same pattern all over again. In other words, for each step k we would need to return getStaircaseCombinations(k-1) + getStaircaseCombinations(k-2) + getStaircaseCombinations(k-3).

At which point do we stop? We know that the combination is correct if the sum of steps a child has made equals exactly to 5. We're going backwards, subtracting from 5 - which means that the correct combination should bring us to 0. So, when we're reaching 0 the combination must be valid and we should return 1. The alternative scenario is that we're ending up with a number less than 0: for instance, a child may have jumped to step 5 from step 2 (n-3) and to step 2 from step -1 (yet again, n-3). However, step -1 does not exist, a child would always start with step 0 - which means our combination does not work. So, for the cases resulting in a negative number we would return 0 and not count such combinations in.

This logic results in:

function getStaircaseCombinations(stairs) {
  if (stairs < 0) { return 0; }
  if (stairs === 0) { return 1; }
  return (
    getStaircaseCombinations(stairs - 1) +
    getStaircaseCombinations(stairs - 2) + 
    getStaircaseCombinations(stairs - 3)
  )
};

Finally, you can notice that in the code above we're calculating the same path several times. For instance, for n=5 you would need to calculate the number of step combinations for 'how to reach step 3' twice: for the case of (n-2) and the case of ((n-1)–1) - and the bigger n gets, the more double-work this code will be doing.

In order to avoid this, we can use memoization technique. The logic is as follows:

✔️start with the empty array of results
✔️if array of results doesn't contain yet the number of combinations for x (and only then!), calculate it and store it in the array as results[x]
✔️return the number of combinations for x stored in the array

The slightly adjusted code that allows for memoization will look like:

function getStaircaseCombinations(stairs) {
  let combinations = [];
  function calculateCombinations(n) {
    if (n < 0) { return 0; }
    if (n === 0) { return 1; }
    if (combinations[n] === undefined) {
      combinations[n] = 
        calculateCombinations(n - 1) + 
        calculateCombinations(n - 2) + 
        calculateCombinations(n - 3);
    }
    return combinations[n];
  };
  calculateCombinations(stairs);
  return combinations[stairs];
}

Comments

[Gunnar Plunkett]

Pretty sure this can be done iteratively in O(1) space, since you actually only need to remember the previous three steps.