Jobs

Interviews

Discussions

Climbing Stairs

Easy

Disney

0 views

Topics:

Dynamic Programming

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?

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

Constraints:

1 <= n <= 45

Climbing Stairs

Easy

Disney

0 views

Topics:

Dynamic Programming

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?

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

Constraints:

1 <= n <= 45

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input `n` guaranteed to be a non-negative integer?
Can `n` be zero? If so, what should the return value be?
For large values of `n`, should I be concerned about integer overflow in my calculations?
Are there any constraints on the time or space complexity of the solution?
Are we only concerned with the number of *distinct* ways, or should I consider other factors?

Brute Force Solution

Approach

To find all the different ways to climb the stairs, we'll try every possible combination of taking one step or two steps at a time. We will explore each path until we reach the top and count valid ways.

Here's how the algorithm would work step-by-step:

Start at the bottom of the stairs.
Consider taking one step.
From that new position, again consider taking either one step or two steps.
Keep repeating the process of choosing one step or two steps from each new position until you either reach the top of the stairs or go past it.
If you reach the top exactly, count that as one way to climb the stairs.
If you go past the top, that's not a valid way, so ignore it.
Go back to the earlier positions and try different step combinations that you have not explored yet.
Repeat the process until you've explored every possible combination of one-step and two-step moves.
The total count of the number of times you landed exactly on the top of the stairs is the answer.

Code Implementation

def climbing_stairs_brute_force(number_of_stairs):
    number_of_ways = 0

    def climb(current_stair):
        nonlocal number_of_ways

        # We reached the top, increment count
        if current_stair == number_of_stairs:
            number_of_ways += 1

        # If we went past the top, this path is invalid
        elif current_stair > number_of_stairs:
            return

        # Explore taking one step
        climb(current_stair + 1)

        # Explore taking two steps
        climb(current_stair + 2)

    climb(0)
    return number_of_ways

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The provided explanation describes a recursive approach where at each step, we have two choices: take one step or take two steps. This branching leads to an exponential number of possible paths. In the worst-case scenario, we explore all possible combinations of one-step and two-step moves. Therefore, the number of paths we explore grows exponentially with the number of stairs (n), resulting in a time complexity of O(2^n).

Space Complexity

O(N) – The dominant space usage comes from the recursion stack. In the worst-case scenario, where we only take one step at a time, the depth of the recursion will be N, where N is the number of stairs. Each recursive call adds a new frame to the stack, consuming memory. Thus, the auxiliary space is proportional to the depth of the recursion which is N, leading to a space complexity of O(N).

Optimal Solution

Approach

The optimal way to solve the climbing stairs problem is to realize you can build up the answer from smaller subproblems. Instead of trying every possible path, you figure out how many ways you can reach each step, and then use that to calculate the total number of ways to reach the top.

Here's how the algorithm would work step-by-step:

Notice that to reach the top step, you can either come from the step just below it, or the step two steps below it.
Think of it this way: the total number of ways to reach the top is the sum of the number of ways to reach those two steps.
So, start from the bottom. There's one way to reach the first step, and two ways to reach the second step (one step at a time or a single jump of two).
Now, to find the number of ways to reach the third step, you add the number of ways to reach the first and second steps.
Continue this pattern: for each step, add the number of ways to reach the previous two steps.
Keep doing this until you reach the top step. The number you calculate for the top step is the total number of ways to climb the stairs.

Code Implementation

def climbing_stairs(number_of_steps):
    if number_of_steps <= 2:
        return number_of_steps

    first_step_ways = 1
    second_step_ways = 2

    # Start from the third step and go to the top.
    for i in range(3, number_of_steps + 1):
        # Ways to reach current step is sum of ways to reach the previous two.
        current_step_ways = first_step_ways + second_step_ways

        first_step_ways = second_step_ways

        # Store the current step's ways for the next calculation.
        second_step_ways = current_step_ways

    return second_step_ways

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates from the third step up to the nth step. In each iteration, it performs a constant number of operations: adding the number of ways to reach the previous two steps. The number of iterations is directly proportional to n, the number of steps. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The plain English explanation outlines an iterative approach where we only need to remember the number of ways to reach the previous two steps to calculate the number of ways to reach the current step. This means we just need to store two variables to hold those counts. The amount of space used by these two variables does not depend on the number of stairs, N, making the space complexity constant.

Edge Cases

Case	How to Handle
n = 0 (No stairs)	Return 1, as there's one way to climb zero stairs (do nothing).
n = 1 (One stair)	Return 1, as there's only one way to climb one stair (take one step).
n = 2 (Two stairs)	Return 2, as there are two ways to climb two stairs (two single steps or one double step).
Large n (Potential for integer overflow)	Use a 64-bit integer type (long in Java/C++) or Python's arbitrary-precision integers to avoid overflow.
Negative n (Invalid input)	Throw an IllegalArgumentException or return an error code indicating invalid input.
Recursive solution exceeding stack limit for very large n	Use dynamic programming (iterative approach) to avoid stack overflow.
Non-integer input for n	Throw an IllegalArgumentException since only integers are valid for the number of stairs.
n equal to the maximum possible integer value	Verify the language used supports incrementing the prior two calculated values without overflow, and handle appropriately.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input `n` guaranteed to be a non-negative integer?
Can `n` be zero? If so, what should the return value be?
For large values of `n`, should I be concerned about integer overflow in my calculations?
Are there any constraints on the time or space complexity of the solution?
Are we only concerned with the number of *distinct* ways, or should I consider other factors?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the bottom of the stairs.
Consider taking one step.
From that new position, again consider taking either one step or two steps.
Keep repeating the process of choosing one step or two steps from each new position until you either reach the top of the stairs or go past it.
If you reach the top exactly, count that as one way to climb the stairs.
If you go past the top, that's not a valid way, so ignore it.
Go back to the earlier positions and try different step combinations that you have not explored yet.
Repeat the process until you've explored every possible combination of one-step and two-step moves.
The total count of the number of times you landed exactly on the top of the stairs is the answer.

Code Implementation

def climbing_stairs_brute_force(number_of_stairs):
    number_of_ways = 0

    def climb(current_stair):
        nonlocal number_of_ways

        # We reached the top, increment count
        if current_stair == number_of_stairs:
            number_of_ways += 1

        # If we went past the top, this path is invalid
        elif current_stair > number_of_stairs:
            return

        # Explore taking one step
        climb(current_stair + 1)

        # Explore taking two steps
        climb(current_stair + 2)

    climb(0)
    return number_of_ways

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Notice that to reach the top step, you can either come from the step just below it, or the step two steps below it.
Think of it this way: the total number of ways to reach the top is the sum of the number of ways to reach those two steps.
So, start from the bottom. There's one way to reach the first step, and two ways to reach the second step (one step at a time or a single jump of two).
Now, to find the number of ways to reach the third step, you add the number of ways to reach the first and second steps.
Continue this pattern: for each step, add the number of ways to reach the previous two steps.
Keep doing this until you reach the top step. The number you calculate for the top step is the total number of ways to climb the stairs.

Code Implementation

def climbing_stairs(number_of_steps):
    if number_of_steps <= 2:
        return number_of_steps

    first_step_ways = 1
    second_step_ways = 2

    # Start from the third step and go to the top.
    for i in range(3, number_of_steps + 1):
        # Ways to reach current step is sum of ways to reach the previous two.
        current_step_ways = first_step_ways + second_step_ways

        first_step_ways = second_step_ways

        # Store the current step's ways for the next calculation.
        second_step_ways = current_step_ways

    return second_step_ways

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0 (No stairs)	Return 1, as there's one way to climb zero stairs (do nothing).
n = 1 (One stair)	Return 1, as there's only one way to climb one stair (take one step).
n = 2 (Two stairs)	Return 2, as there are two ways to climb two stairs (two single steps or one double step).
Large n (Potential for integer overflow)	Use a 64-bit integer type (long in Java/C++) or Python's arbitrary-precision integers to avoid overflow.
Negative n (Invalid input)	Throw an IllegalArgumentException or return an error code indicating invalid input.
Recursive solution exceeding stack limit for very large n	Use dynamic programming (iterative approach) to avoid stack overflow.
Non-integer input for n	Throw an IllegalArgumentException since only integers are valid for the number of stairs.
n equal to the maximum possible integer value	Verify the language used supports incrementing the prior two calculated values without overflow, and handle appropriately.