paint-brush
Solving The Staircase Problem With Just 5 Linesby@indepthjavascript
304 reads
304 reads

Solving The Staircase Problem With Just 5 Lines

by Amit MehtaJuly 21st, 2022
Read on Terminal Reader
Read this story w/o Javascript
tldt arrow

Too Long; Didn't Read

Staircase Programming Challenge: How many different ways can you reach the top of the stairs? How many ways you can take 1, 2, or 3 steps at a time? There is a simple way to solve this problem using everyone's favorite algorithm: **recursion. Here is the solution in 5 lines of JavaScript code: stepTaken is a counter for steps taken in each combination. It's tricky for sure, but once you understand it, it opens up a whole new world of possibilities!

Company Mentioned

Mention Thumbnail
featured image - Solving The Staircase Problem With Just 5 Lines
Amit Mehta HackerNoon profile picture


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.


  1. 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. 🤓