Solving The Staircase Problem With Just 5 Lines

If you're new to algorithms and leetcode, the staircase problem is infamous!

😬

What is the Staircase Programming Challenge?

Stated simply....

Imagine a staircase with N steps. If you can take 1, 2, or 3 steps at a time, how many different ways can you reach the top of the stairs?

Encountering a problem like this for the first time is for sure frightening. Even on its own as a math problem, IT'S REALLY HARD.

There are a few obvious cases. You can take 1 step at a time, N times. If N is divisible by 2, you can take 2 steps, N/2 times. Also, if N is divisible by 3, you can take 3 steps, N/3 times.

And then there is everything in between. 🤔

The good news is there is a really simple way to solve this problem using everyone's favorite algorithm: recursion. 😨

Recursion to the Rescue

As promised, here is the solution in 5 lines of JavaScript code...

// N is total number of steps in the staircase
// stepTaken is a counter for steps taken in each combination
function steps(N, stepsTaken = 0) {

  if (stepsTaken === N) return 1;
  else if (stepsTaken > N) return 0;

  return steps(N,stepsTaken + 1) + steps(N,stepsTaken + 2) + steps(N,stepsTaken + 3);
}

Yikes! What does this mean??

Don't panic or feel bad if the above code confuses you. I struggled for a long time with recursion since I first learned it in high school CS class. It's tricky for sure. But once you understand it, it opens up a whole new world of possibilities!

Let's walk through this solution

If you're thinking of just copying the above solution and leaving, you're missing the point. It's super important you understand what's happening.

function steps(N, stepsTaken = 0) is just a simple recursive counter.

Let's walk through it:

1. We're at the bottom of the stairs, no steps taken. So stepsTaken = 0.

2. You have 3 possibilities in front of you: take 1 step, jump up 2 steps, or leap up 3 steps.

3. Now we need to account for ALL 3 possibilities. So imagine you clone the stairs and yourself 2 times. Plus, you each have your own version of stepsTaken variable you’re carrying with you. You and your clones each go through one of these 'doors' (note each of you must go through a DIFFERENT door):

   
   

steps(N,stepsTaken + 1)
steps(N,stepsTaken + 2)
steps(N,stepsTaken + 3)

Once you go through your chosen door, your individual stepsTaken counter will be incremented by 1, 2, or 3 (depending on the door you went through). Then after that, you'll immediately see 3 more doors:

steps(N,stepsTaken + 1)
steps(N,stepsTaken + 2)
steps(N,stepsTaken + 3)

Again, you'll clone yourself 2 times again and each go through one of these steps doors. Your stepsTaken counter will increment again by 1, 2, or 3. This will KEEP HAPPENING until:

  if (stepsTaken === N) return 1;
  else if (stepsTaken > N) return 0;

If you overstepped stepsTaken > N, your combination of steps does NOT count towards the total of unique ways to go up the stairs.

However, if (stepsTaken === N), then bingo 🤩 you found a legit combo of steps to go up the stairs, and you return 1 to add to the count of ways to go up the stairs.

5. Now remember the way we count the number of possible combinations of stepsTaken to reach the top of the N step staircase is to simply add all the possibilities:

   
   

return steps(N,stepsTaken + 1) + steps(N,stepsTaken + 2) + steps(N,stepsTaken + 3);

Remember each legitimate combo of steps where if (stepsTaken === N) return 1 and each if path is not valid (overstep) then 0 is returned : else if (stepsTaken > N) return 0.

Some of you may be asking: Nice, this is elegant, but isn't it super inefficient in terms of time complexity?

Yea, it's super high time complexity. However, there's a trick to dramatically improving that ➡️ How to Solve the Staircase Problem with JavaScript using Memoization

Hope this makes sense, comment below if you have any questions?

If you enjoyed this article, please check out my blog Indepth JavaScript for more illuminating content. 🤓