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(2n)O(2^n). Using dynamic programming reduces this to O(n)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.

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 nn 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≤n≤1031 \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.

Knowledge test

Now that we understand the problem, let’s test our knowledge by finding the total number of ways to reach the top when nn = 4:

Solution to the Climbing Stairs problem

Intuition behind the solution:

We'll start with discussing a few examples.

• For a staircase with 1 step, nn = 1, there’s only one way to reach the top—take 1 step once.

• For a staircase with 2 steps, nn = 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, nn = 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 nn = 3, note that the first way can be seen as taking 1 step from nn = 1 plus an additional 2 steps at once. The second and third ways are extensions of the ways for nn = 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 nn = 3 is nothing but the number of ways for nn = 2 and the number of ways for nn = 1 ( in place of the extra step). So now, we can write the number of ways for nn = 3 as:

• Number of ways for nn = 2 + Number of ways for nn = 1 → 2 + 1 → 3

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

• Number of ways for nn = 3 + Number of ways for nn = 2 → 3 + 2 → 5

This is not a coincidence, but a pattern that underlies—for every nn, 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 nn steps is the sum of the number of ways for nn-1 and nn-2.

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 nn.

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−1n-1 and n−2n-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−1n-1 steps, and the second represents the number of ways to reach the n−2n-2 steps.

• Use a loop that goes from 2 to nn, and for each nn:

  • 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 nn 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.

Time complexity

The loop runs from 2 to nn, 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)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 nn. There are no data structures like arrays or lists that grow with nn. Therefore, the overall space complexity is O(1)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:

1. Unique Paths: Given a grid of mm x nn, find the number of unique paths from the top-left corner to the bottom-right corner, where you can only move down or right.

2. 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.

3. 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.

4. 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'.

5. 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].