If you're new to algorithms and leetcode, the staircase problem is infamous!
😬
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. 😨
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);
}
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!
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:
We're at the bottom of the stairs, no steps taken. So stepsTaken = 0
.
You have 3 possibilities in front of you: take 1 step, jump up 2 steps, or leap up 3 steps.
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.
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. 🤓