Jobs

Interviews

Discussions

Climbing Stairs

Easy

Uber

1 view

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

Uber

1 view

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:

What is the maximum possible value of n? Can I assume it will fit within the bounds of an integer?
Is n guaranteed to be a positive integer, or could it be zero or negative?
Should I return the number of ways as an integer, or could it be a very large number that requires a different data type (e.g., long)?
Could you provide a few example inputs and expected outputs for small values of n (e.g., n=0, n=1, n=2, n=3) to ensure I understand the problem correctly?
Are there any constraints on the time or space complexity of my solution?

Brute Force Solution

Approach

Imagine you're climbing a staircase and can take either one or two steps at a time. The brute force way is to try every single possible combination of single and double steps to reach the top. We'll count each unique path.

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

Start at the bottom of the stairs.
Try taking one step. From there, explore all possible ways to reach the top, taking one or two steps at a time.
Now, go back to the bottom and try taking two steps. Again, explore all possible ways to reach the top from there, using one or two steps at a time.
Continue exploring every single possible combination of one-step and two-step moves until you've considered all paths.
Each time you reach the top of the stairs, count that as one successful way to climb the stairs.
In the end, the total count of all these successful ways represents the answer to how many different ways you can climb the stairs.

Code Implementation

def climbing_stairs_brute_force(number_of_stairs):
    def count_ways(current_step):
        # If we've reached the top, it's a valid way
        if current_step == number_of_stairs:
            return 1

        # If we've overshot, it's not a valid way
        if current_step > number_of_stairs:
            return 0

        # Explore taking one step
        one_step = count_ways(current_step + 1)

        # Explore taking two steps
        two_steps = count_ways(current_step + 2)

        # Accumulate the total ways to reach the top
        return one_step + two_steps

    # Start from the bottom (step 0)
    return count_ways(0)

Big(O) Analysis

Time Complexity

O(2^n) – The given brute force approach explores all possible combinations of 1-step and 2-step moves to reach the top of the staircase. For each step, we have two choices: take one step or take two steps. In the worst case, we might have to explore all possibilities, leading to a branching factor of 2 for each step. Therefore, the number of possible paths grows exponentially with the number of steps, n. This creates a binary tree-like structure of possible paths, where the height of the tree is proportional to n and each node represents a choice between one or two steps. This results in approximately 2^n operations, which makes the time complexity O(2^n).

Space Complexity

O(N) – The brute force approach described involves exploring every possible combination of one-step and two-step moves, effectively creating a decision tree. The maximum depth of this recursion tree is N, where N is the number of stairs. Each level of the recursion adds a new stack frame to the call stack, resulting in a space complexity proportional to the maximum recursion depth. Therefore, the auxiliary space required is O(N) due to the recursion call stack.

Optimal Solution

Approach

The problem involves finding the number of ways to climb a staircase with only one or two steps at a time. Instead of exploring every single combination, we can use a more efficient method based on recognizing a pattern. This strategy builds the solution from the ground up by reusing previously computed results.

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

Think about the simplest cases: How many ways are there to climb 1 step? How many ways are there to climb 2 steps?
Now, consider how the number of ways to reach a certain step relates to the number of ways to reach the steps before it.
To reach any step, you can either take one step from the previous step, or two steps from two steps before.
So, the number of ways to reach a given step is simply the sum of the ways to reach the step before it and the step two steps before it.
Start with the base cases (1 step and 2 steps) and use them to calculate the number of ways for each subsequent step, working your way up to the total number of steps.
By storing the results for smaller steps, we avoid recalculating them and can quickly find the answer for the total number of steps.

Code Implementation

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

    # Initialize base cases for 1 and 2 steps
    step_one_count = 1
    step_two_count = 2

    # Iterate from 3 up to the total number of steps.
    for i in range(3, number_of_steps + 1):

        # Calculate ways to reach current step.
        current_step_count = step_one_count + step_two_count

        # Update variables for next iteration.
        step_one_count = step_two_count
        step_two_count = current_step_count

    # The accumulated value holds the total number of ways.
    return step_two_count

Big(O) Analysis

Time Complexity

O(n) – The solution iterates from step 3 up to the target number of steps, n. Within the loop, it performs a constant amount of work, specifically addition. Since the number of iterations is directly proportional to n, the time complexity grows linearly with the input size. Thus, the algorithm's time complexity is O(n).

Space Complexity

O(N) – The described dynamic programming approach calculates the number of ways to climb the stairs iteratively from the base cases (1 and 2 steps) up to N steps. This requires storing the results for each step along the way to avoid recalculating them, implying that we need memory to store intermediate results from 1 to N. Therefore, an auxiliary data structure, such as an array or variables, is needed to store these values from 1 up to N and grows linearly with the number of steps N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
n = 0	Return 1, as there is one way to climb 0 stairs (do nothing).
n = 1	Return 1, as there is one way to climb 1 stair (take one step).
n = 2	Return 2, as there are two ways to climb 2 stairs (two single steps or one double step).
Large n (potential integer overflow)	Use a data type capable of holding larger values, such as long or consider using a library for arbitrary-precision arithmetic if necessary.
Negative n (invalid input)	Throw an IllegalArgumentException or return 0, indicating invalid input.
Algorithm-specific recursion depth for very large n (if using recursion)	Implement dynamic programming or iteration to avoid stack overflow issues.
Memoization table size in dynamic programming (if using dynamic programming)	Ensure sufficient memory is allocated for the memoization table to store intermediate results for all possible stair counts up to n.
Input 'n' is significantly large such that generating fibonacci sequence via recursion gives StackOverflowError	Use iterative approach, dynamic programming, or memoization to avoid recursion.

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:

What is the maximum possible value of n? Can I assume it will fit within the bounds of an integer?
Is n guaranteed to be a positive integer, or could it be zero or negative?
Should I return the number of ways as an integer, or could it be a very large number that requires a different data type (e.g., long)?
Could you provide a few example inputs and expected outputs for small values of n (e.g., n=0, n=1, n=2, n=3) to ensure I understand the problem correctly?
Are there any constraints on the time or space complexity of my solution?

Brute Force Solution

Approach

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

Start at the bottom of the stairs.
Try taking one step. From there, explore all possible ways to reach the top, taking one or two steps at a time.
Now, go back to the bottom and try taking two steps. Again, explore all possible ways to reach the top from there, using one or two steps at a time.
Continue exploring every single possible combination of one-step and two-step moves until you've considered all paths.
Each time you reach the top of the stairs, count that as one successful way to climb the stairs.
In the end, the total count of all these successful ways represents the answer to how many different ways you can climb the stairs.

Code Implementation

def climbing_stairs_brute_force(number_of_stairs):
    def count_ways(current_step):
        # If we've reached the top, it's a valid way
        if current_step == number_of_stairs:
            return 1

        # If we've overshot, it's not a valid way
        if current_step > number_of_stairs:
            return 0

        # Explore taking one step
        one_step = count_ways(current_step + 1)

        # Explore taking two steps
        two_steps = count_ways(current_step + 2)

        # Accumulate the total ways to reach the top
        return one_step + two_steps

    # Start from the bottom (step 0)
    return count_ways(0)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Think about the simplest cases: How many ways are there to climb 1 step? How many ways are there to climb 2 steps?
Now, consider how the number of ways to reach a certain step relates to the number of ways to reach the steps before it.
To reach any step, you can either take one step from the previous step, or two steps from two steps before.
So, the number of ways to reach a given step is simply the sum of the ways to reach the step before it and the step two steps before it.
Start with the base cases (1 step and 2 steps) and use them to calculate the number of ways for each subsequent step, working your way up to the total number of steps.
By storing the results for smaller steps, we avoid recalculating them and can quickly find the answer for the total number of steps.

Code Implementation

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

    # Initialize base cases for 1 and 2 steps
    step_one_count = 1
    step_two_count = 2

    # Iterate from 3 up to the total number of steps.
    for i in range(3, number_of_steps + 1):

        # Calculate ways to reach current step.
        current_step_count = step_one_count + step_two_count

        # Update variables for next iteration.
        step_one_count = step_two_count
        step_two_count = current_step_count

    # The accumulated value holds the total number of ways.
    return step_two_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0	Return 1, as there is one way to climb 0 stairs (do nothing).
n = 1	Return 1, as there is one way to climb 1 stair (take one step).
n = 2	Return 2, as there are two ways to climb 2 stairs (two single steps or one double step).
Large n (potential integer overflow)	Use a data type capable of holding larger values, such as long or consider using a library for arbitrary-precision arithmetic if necessary.
Negative n (invalid input)	Throw an IllegalArgumentException or return 0, indicating invalid input.
Algorithm-specific recursion depth for very large n (if using recursion)	Implement dynamic programming or iteration to avoid stack overflow issues.
Memoization table size in dynamic programming (if using dynamic programming)	Ensure sufficient memory is allocated for the memoization table to store intermediate results for all possible stair counts up to n.
Input 'n' is significantly large such that generating fibonacci sequence via recursion gives StackOverflowError	Use iterative approach, dynamic programming, or memoization to avoid recursion.