Climbing Stairs LeetCode

Key takeaways:
Recognize the Fibonacci pattern: The Climbing Stairs problem follows a recurrence relation similar to the Fibonacci sequence, where each step is the sum of the previous two steps.
Dynamic programming for efficiency: The naive recursive solution for Climbing Stairs explores all possible ways to reach the top, resulting in repeated calculations and an exponential time complexity of $O(2^n)$ . Using dynamic programming reduces this to $O(n)$ by storing and reusing subproblem results.
Interview preparation tip: Practice Climbing Stairs and similar dynamic programming problems to build the skill of breaking down complex problems—essential in coding interviews and real-world optimization tasks.

Climbing Stairs is one of the frequently asked coding question by top tech companies like GoogleGoogle asked it 27 times as of October 2024. [LeetCode], AmazonAmazon asked it 11 times as of October 2024. [LeetCode], MicrosoftMicrosoft asked it 9 times as of October 2024. [LeetCode], AccentureAccenture asked it 6 times as of October 2024. [LeetCode], MetaMeta asked it 5 times as of October 2024. [LeetCode], ZohoZoho asked it 4 times as of October 2024. [LeetCode], AppleApple asked it 3 times as of October 2024. [LeetCode], TikTokTikTok asked it 3 times as of October 2024. [LeetCode], IBMIBM asked it 2 times as of October 2024. [LeetCode], and AdobeAdobe asked it 2 times as of October 2024. [LeetCode].

The Climbing Stairs problem is an important one to practice for technical interviews because it covers skills that companies like Meta, Amazon, Apple, Google, and Microsoft (MAANG) often test. This problem introduces you to dynamic programming, a key technique for solving tricky and complex coding problems more efficiently. It also builds your ability to recognize patterns, like the Fibonacci sequence, which comes up often in coding challenges.

The climbing stairs is a simple, but really valuable for interview prep. By practicing this problem, you’ll gain confidence and be better prepared for tougher, more advanced problems in technical interviews. Let's walk through the solution to this problem, covering the algorithm steps, code, and a time and space complexity analysis.

Problem statement

You are climbing a staircase with $n$ steps. You can take either 1 step or 2 steps at a time. The task is to calculate how many different ways you can reach the top of the staircase. For example, for a staircase with 2 steps, you can either take 1 step twice or 2 steps once.

Constraints:

$1 \leq n \leq 10^3$
You can only take 1 step or 2 steps at a time.

Let's look at the following examples to better understand the problem.

Solution to the Climbing Stairs problem

Intuition behind the solution:

We'll start with discussing a few examples.

For a staircase with 1 step, $n$ = 1, there’s only one way to reach the top—take 1 step once.
For a staircase with 2 steps, $n$ = 2, we can take:
- 1 step twice, i.e., 1 step + 1 step
- 2 steps at once, i.e., 2 steps
For a staircase with 3 steps, $n$ = 3, we can take:
- 1 step once and 2 steps once, i.e., 1 step + 2 steps
- 1 step thrice, i.e., 1 step + 1 step + 1 step
- 2 steps once and 1 step once, i.e., 2 steps + 1 step

Now, for $n$ = 3, note that the first way can be seen as taking 1 step from $n$ = 1 plus an additional 2 steps at once. The second and third ways are extensions of the ways for $n$ = 2: one way involves taking 1 step twice with an extra step, and the other involves taking 2 steps at once with an extra step. To simplify it further, we can say that the number of ways for $n$ = 3 is nothing but the number of ways for $n$ = 2 and the number of ways for $n$ = 1 ( in place of the extra step). So now, we can write the number of ways for $n$ = 3 as:

Number of ways for $n$ = 2 + Number of ways for $n$ = 1 → 2 + 1 → 3

Similarly, for $n$ = 4, we can write the number of ways as:

Number of ways for $n$ = 3 + Number of ways for $n$ = 2 → 3 + 2 → 5

This is not a coincidence, but a pattern that underlies—for every $n$ , 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. In other words, the total number of ways for a staircase with $n$ steps is the sum of the number of ways for $n$ -1 and $n$ -2.

Do you see what pattern this is? Yes, it’s the well-known Fibonacci sequenceThe Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1 (e.g., 0, 1, 1, 2, 3, 5, 8, 13, ...)..

Let's look at the following illustration for a better understanding.

Algorithm

In this solution, we use the iterative dynamic programming approach—bottom-up. In a bottom-up approach, we start solving the smallest subproblems first and use their solutions to build up to the larger problem. In this case, the code starts with the number of ways to reach the first two steps and then iteratively calculates the number of ways for higher steps until it reaches $n$ .

Instead of calculating the ways to reach each step from scratch, the code builds on the solutions for earlier steps, which is a key idea in dynamic programming. By storing just the last two results, the ways to reach $n-1$ and $n-2$ , instead of all previous steps, the code saves memory and makes the process faster.

Now, let's go over the algorithm steps:

Create and initialize two variables, ways_n_1 and ways_n_2, to 1. The first one represents the number of ways to reach the $n-1$ steps, and the second represents the number of ways to reach the $n-2$ steps.
Use a loop that goes from 2 to $n$ , and for each $n$ :
- Calculate the number of ways to reach the current step, current_number_of_ways, by adding ways_n_1 and ways_n_2.
- Update the values of ways_n_1 and ways_n_2.
  - Assign ways_n_2 the value of ways_n_1.
  - Assign ways_n_1 the value of current_number_of_ways.
Once the loop is finished, ways_n_1 will hold the total number of ways to reach the top of the staircase with $n$ steps.

Python code to solve Climbing Stairs problem

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

def climbing_stairs(n):
    # Stores the total ways to climb n - 1 steps
    ways_n_1 = 1
    # Stores the total ways to climb n - 2 steps
    ways_n_2 = 1
    # Loop over the total single steps needed to reach the top for n steps
    for _ in range(2, n + 1):
      
        # Current_number_of_ways stores the sum of the previous two terms 
        current_number_of_ways = ways_n_1 + ways_n_2
        
        # Update the value of ways_n_2 to ways_n_1 and ways_n_1 to current_number_of_ways        
        ways_n_2 = ways_n_1
        ways_n_1 = current_number_of_ways 
    # In the end, ways_n_1 will store the total steps to reach the top on n stairs
    return ways_n_1
# Driver code
def main():
    test_cases = [1, 2, 3, 4, 5, 6, 7, 8]  # List of different values of n to test
    
    for n in test_cases:
        result = climbing_stairs(n)
        print(f"Total number of ways for n = {n} : {result}")
        print("-"*100)
if __name__ == "__main__":
    main()

Climbing Stairs LeetCode

Time complexity

The loop runs from 2 to $n$ , and inside the loop, we perform a constant amount of work (adding two numbers and updating variables) for each step. Therefore, the overall time complexity of this solution is $O(n)$ .

Space complexity

We only use a fixed amount of space for the variables ways_n_1, ways_n_2, and current_number_of_ways, regardless of the input size $n$ . There are no data structures like arrays or lists that grow with $n$ . Therefore, the overall space complexity is $O(1)$ .

Coding problems similar to Climbing Stairs

Some coding problems that are similar to the Climbing Stairs problem, often involving dynamic programming or recursive approaches:

Unique Paths: Given a grid of $m$ x $n$ , find the number of unique paths from the top-left corner to the bottom-right corner, where you can only move down or right.
Coin Change: Given a set of coin denominations and a total amount, determine the number of different ways to make that amount using the given coins.
House Robber: You are a burglar trying to rob houses arranged in a circle. If you rob two adjacent houses, you trigger an alarm. Find the maximum amount of money you can rob without triggering the alarm.
Decode Ways: Given a string containing digits, determine the total number of ways to decode it where '1' maps to 'A', '2' maps to 'B', and so on up to '26' mapping to 'Z'.
Longest Increasing Subsequence: Given an array of integers, find the length of the longest increasing subsequence.

If you're looking to practice more of these coding problems, Educative offers a comprehensive course dedicated to dynamic programming coding problems. For every coding problem, it has covered three solution approaches—the naive, the top-down, and the bottom-up—along with their complexity analysis. You can find the course [here].

On that note, take a look at some other Answers that cover solutions to frequently asked LeetCode problems in detail:

If you think you're done preparing for the technical interview, try attempting Educative's AI-empowered mock interviews. Mock interviews, in general, help you build confidence, improve your problem-solving skills, and identify areas where you can improve before the actual interview.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

How is the Climbing Stairs problem related to the Fibonacci sequence?

The problem follows a pattern where the number of ways to reach step n is the sum of the ways to reach step $n$ -1 and step $n$ -2, which is exactly how the Fibonacci series is constructed.

What is the formula for the climbing stairs problem?

The formula for the Climbing Stairs problem is based on the Fibonacci sequence. If you can take either 1 or 2 steps at a time, then the number of ways to reach the top of a staircase with n steps is:

f( $n$ )=f( $n$ −1)+f( $n$ −2)

Where:

f( $n$ ) is the total number of ways to climb n steps.
f( $n$ -1) represents the number of ways to reach the top if you take 1 step from step $n$ -1.
f( $n$ -2) represents the number of ways to reach the top if you take 2 steps from step $n$ -2.

Base cases:

f(1) = 1 (1 way to climb 1 step)
f(2) = 2 (2 ways to climb 2 steps: two 1-steps or one 2-step)

This formula is derived from the idea that at each step, you either came from $n$ -1 or $n$ -2.

What is the recursive solution for climbing stairs?

The recursive solution for the Climbing Stairs problem involves calculating the number of ways to reach the top by recursively summing the ways to climb $n$ -1 and $n$ -2 steps:

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

This approach follows the Fibonacci pattern but has a high time complexity of $O(2^n)$ due to repeated calculations.

Why is dynamic programming important for solving coding problems?

Dynamic programming is important for solving problems like Climbing Stairs because it breaks the problem into smaller sub-problems and uses the results of these sub-problems to efficiently build the main solution, avoiding redundant calculations. This prevents redundant computations, improving both time and space efficiency—key skills tested in coding interviews at top tech companies.

How to prepare for a dynamic programming interview?

To prepare for a dynamic programming (DP) interview, focus on understanding the key concepts like memoization, tabulation, and breaking down problems into overlapping sub-problems. Practice the following top frequently asked dynamic programming problems to enhance your preparation:

Longest Common Subsequence (LCS)
Knapsack Problem
Coin Change
House Robber
Fibonacci Number
Longest Increasing Subsequence (LIS)
Edit Distance
Unique Paths
Partition Equal Subset Sum
Palindrome Partitioning

Work on these problems, understand their patterns, and practice multiple variations to build your dynamic programming skills.

Free Resources

Climbing Stairs LeetCode

Problem statement

Knowledge test

Solution to the Climbing Stairs problem

Algorithm

Python code to solve Climbing Stairs problem

Time complexity

Space complexity

Coding problems similar to Climbing Stairs

Frequently asked questions

How is the Climbing Stairs problem related to the Fibonacci sequence?

What is the formula for the climbing stairs problem?

What is the recursive solution for climbing stairs?

Why is dynamic programming important for solving coding problems?

How to prepare for a dynamic programming interview?