[Interview Question] The Climbing Stairs Problem

Company Tags: Amazon, Apple, Adobe, Microsoft, Bloomberg, Goldman Sachs

Problem Statement:

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Constraints:
1 <= n <= 45

Examples

Let us look at some examples to improve our understanding of the problem.

Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Example 3:
Input: n = 1
Output: 1
Explanation: There is only one way to climb to the top.
1. 1 step 

Example 4:
Input: n = 4
Output: 5
Explanation: There are five ways to climb to the top.
1 step + 1 step + 1 step + 1 step
2 steps + 1 step + 1 step
1 step + 1 step + 2 steps
1 step + 2 steps + 1 step
2 steps + 2 steps

Now that you have a clear understanding of the problem, let’s dive into the various methods to solve it.

Method 1: Recursive Approach

Approach: The idea in this approach is to use recursion to solve this problem. To reach the top stair given by n, you can reach the nth stair by climbing it either from the (n-1)th stairs or (n-2)th stair. Therefore, for every top stair n, you should find the number of ways you can reach the n-1th stair and the number of ways you can reach the n-2th stair and then add them up to find the total number of ways available.

ways to reach level n = ways to reach level (n - 1) + ways to reach level (n - 2)

Therefore, if you keep finding the number of ways a particular step can be reached based on a top to down approach in a recursive manner, then you will eventually reach the final output. Let’s have a look at the following recursion tree diagram to understand this approach:

In the above example, the top stair is 4. Now, you can reach:

  • The 4th stair from the 3rd stair or you can reach it from the 2nd stair. Hence, we have two ways to reach stair four from either star 2 or stair 3.
  • The 3rd stair can be reached in two ways: (i) stair 2 –> stair 3 (ii) stair 1 –> stair 3
  • The 2nd stair can be reached in two ways again. (i) Directly from level 0 (ground). (ii) level 0 –> stair1 –> stair 2
  • Finally, there is only one way to reach stair 1: level 0 –> stair 1

Therefore, number of ways to reach stair 4 = 2+2+1 = 5 (output).

Now, let’s have a look code to implement the algorithm explained above:

def climb_stairs(n):
    if n <= 1:
        return n
    return climb_stairs(n - 1) + climb_stairs(n - 2)
def no_of_ways(n):
    return climb_stairs(n + 1)

Test Case Analysis: Let’s run the code on our examples to check if it works.

# Example 1
n = 2
print(climb_stairs(n))
# 2

# Example 2
n = 3
print(climb_stairs(n))
# 3

# Example 3
n = 1
print(climb_stairs(n))
# 1

# Example 4
n = 4
print(climb_stairs(n))
# 5
Hurrah! Our code passed all the test cases.

Complexity Analysis

  • Time Complexity: In this approach, we have to either climb one stair or climb two stairs recursively. Hence, the time complexity of this method would be O(2 ^ n) or exponential.
  • Space Complexity: The space complexity of this algorithm is O(n).

Discussion: Since you have to use recursion in this approach, the function calls itself again and again. Also, it has the disadvantage of recomputing the values at the lower levels. If you have a look at the tree in the example above, you will find that the function calls itself twice for the value 2. This is unnecessary and repetitive that hampers the overall efficiency of the code leading to an overall complexity of 2n . So, in the next approach, you will find out how you can eliminate unnecessary repetitions from your algorithm and improve the overall complexity of your code.

Method 2: Iterative Approach [Dynamic Programming]

Approach: The idea here is use to a bottom-up approach. The question is basically a modification of the Fibonacci Sequence problem. Of course, you wouldn’t know that just by reading the problem. But that’s why practice makes a man perfect. Let’s understand how it actually represents the Fibonacci series.

Let’s say that there are 5 steps. Now,
⦿ No. of ways to climb to step 5 = 8
⦿ No. ways to climb to step 4 = 5
⦿ No. of ways to climb to step 3= 3
⦿ No. of ways to climb to step 2 = 2
⦿ No. of ways to climb to step 1 = 1

Now, in the given question, the stairs start from 1. Hence, in this case, you have to start computing the values from 1 and 2. The algorithm calculates the next element of the series as the sum of both last elements. For this, the algorithm has to keep track only of the last two elements in the series. Thus, we maintain two variables: a and b, being the second last and last element in the series, respectively. This ensures that you do not have to recursively call the function again and again.

The following code implements the approach explained above:

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for i in range(3, n):
        temp = b
        b = a + b
        a = temp
    return a+b

Test Case Analysis: Let’s run the code on our examples to check if it works.

# Example 1
n = 2
print(climb_stairs(n))
# 2

# Example 2
n = 3
print(climb_stairs(n))
# 3

# Example 3
n = 1
print(climb_stairs(n))
# 1

# Example 4
n = 4
print(climb_stairs(n))
# 5
Hurrah! Our code passed all the test cases.

Complexity Analysis: The time complexity of the iterative approach as seen above is linear, as it iterates from 3 to n, i.e., it runs in O(n) time.

Bonus: How to Store First n Fibonacci Numbers in a List?

Recap, the Fibonacci series is the series of numbers that arises when repeatedly summing up the last two numbers starting from 0 and 1. Here’s an algorithm that stores the first n Fibonacci numbers in a list and returns the list:

def fibo(n):
    result = []
    a, b = 0, 1
    while a < n:
        result.append(a)
        a, b = b, a+b
    return result

fib100 = fibo(100)
print(fib100[-1]== fib100[-2]+fib100[-3])
# True

The fibo function in the code calculates all Fibonacci numbers up to the function argument n.

Here we used multiple assignments to store the value of b in the variable a and to calculate the new value of b as the sum of both. We maintain the whole sequence in the list variable result by appending the sequence value a to the end of the list.

The code calculates the Fibonacci sequence up to 100 and stores the whole list in the variable fib100. But to understand the code, you do not have to calculate the whole sequence. The print statement only compares whether the last element is equal to the sum of the second and third last element in the sequence. This is true by definition of the Fibonacci series.

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.


Recommended: Finxter Computer Science Academy

  • One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in today’s world that’s shaped by the web and remote work.
  • So, do you want to master the art of web scraping using Python’s BeautifulSoup?
  • If the answer is yes – this course will take you from beginner to expert in Web Scraping.