Climbing Stairs LeetCode

The climbing stairs LeetCode problem is a common interview problem that embodies an example where a coder has to combine a set of decisions under certain constraints. The problem demands us to determine the number of ways we can climb a staircase with ${n}$ number of steps. There are many ways to approach this problem, but the most space-optimized solution implements the Fibonacci series as explained in the following discussion.

Problem statement

Let’s look at the problem in detail. The problem creates a scenario of having to climb a staircase. This staircase has total of ${n}$ steps. We can take a single step or two at once to reach the top. The problem demands us to calculate the total number of unique ways to reach the top.

Constraints:

• $1 \leq n \leq 10^3$

• Climb one or two stairs at once

Inspect the slides below to better visualize the problem statement.

Knowledge test

Now that we’ve understood the problem, let’s check our knowledge by finding the total ways to reach the top of the example below:

Algorithm for climbing stairs

If we observe the above examples, we’ll notice a strange pattern: the total number of ways to get to the top is equal to the sum of the previous two consecutive ways to reach the top. This is demonstrated with the following illustration:

Does it sound like the Fibonacci series? Well, it is.

Here’s how we determine the number of ways to reach the top with $n$ steps:

1. We loop over the total number of single steps needed to reach the top: ${n-1}$.

2. We then sum the previous two terms: ways taken to reach the top when the step count is ${n-1}$ and ${n-2}$. We store the sum in the variable current_number_of_ways. The number of ways for ${n-1}$ is stored in the variable consecutive_1 and that for ${n-2}$ is stored in consecutive_2.

3. Next, we replace/update the value of consecutive_2 with consecutive_1.

4. Lastly, we replace/update the value of consecutive_1 with current_number_of_ways.

Code implementation

Let’s look at the code for the above algorithm that implements the Fibonacci series to calculate the total number of ways to reach the top.

Code explanation

• Lines 1–6: We define a function called educatives_ways_to_reach_on_top() and pass the total number of steps in the staircase to it. Then, we initialize two variables consecutive_1 for n – 1 and consecutive_2 for n – 2 with the value 1.

• Lines 9–14: Next, we iterate over the total number of jumps needed to reach the top when there are n steps. We store the sum of consecutive_1 and consecutive_2 in the variable current_number_of_ways. After that, we update the values of consecutive_2 with consecutive_1 and consecutive_1 with current_number_of_ways.

• Lines 19–22: This code section tests the function we defined above. We can pass it any value of n.

Time complexity

It shouldn’t be surprising to know that the time complexity of this algorithm is, in fact, ${O(n)}$. This is because we iterate over the total single jumps required to reach the top in a single for loop: ${n-1}$.

Space complexity

The space complexity is $O(1)$ because as the number of steps in the staircase grows, the space required to compute the total ways remains constant, which means no additional variables are created as the value of $n$grows.