Climbing Stairs – Solution & Complexity

Q: What is the time and space complexity of Climbing Stairs?

The optimal Climbing Stairs solution runs in `O(n)` time and `O(1)` space. DP where ways(n) = ways(n-1) + ways(n-2), kept in two rolling variables (Fibonacci).

Q: What is the most efficient way to solve Climbing Stairs?

DP where ways(n) = ways(n-1) + ways(n-2), kept in two rolling variables (Fibonacci). This gives `O(n)` time complexity, and is a classic math and dynamic programming problem.

Q: How do you solve Climbing Stairs in Python & JavaScript?

We provide a worked Climbing Stairs solution in Python & JavaScript with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Climbing Stairs an easy or hard interview question?

Climbing Stairs is generally rated **Easy**. It tests math and dynamic programming, which are common coding-interview patterns.

1. Understand the Choices

At each move, you can climb either 1 step or 2 steps.
To reach step n, the last move must come from step n - 1 or step n - 2.
Therefore, ways to reach n equals ways to reach n - 1 plus ways to reach n - 2.

2. Recognize the Fibonacci Pattern

For n = 1, there is 1 way: 1.
For n = 2, there are 2 ways: 1+1 and 2.
Every later answer is the sum of the previous two answers.

3. Avoid Recomputing Subproblems

A naive recursive solution branches into n - 1 and n - 2 repeatedly.
That repeats the same calculations many times.
Dynamic programming stores or carries forward the previous answers instead.

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

4. Keep Only the Last Two Values

You do not need a full array because each state depends only on the previous two states.
Let one_back represent ways to reach the previous step.
Let two_back represent ways to reach the step before that.

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    two_back = 1
    one_back = 2
    return one_back

5. Final Solution and Complexity

Iterate from step 3 through step n, adding the last two counts each time.
Time complexity is O(n).
Space complexity is O(1) because only two counts are stored.

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n

    two_back = 1
    one_back = 2
    for _ in range(3, n + 1):
        current = one_back + two_back
        two_back = one_back
        one_back = current

    return one_back

Climbing Stairs – Solution & Complexity

1. Understand the Choices

2. Recognize the Fibonacci Pattern

3. Avoid Recomputing Subproblems

4. Keep Only the Last Two Values

5. Final Solution and Complexity

FAQ

What is the time and space complexity of Climbing Stairs?

What is the most efficient way to solve Climbing Stairs?

How do you solve Climbing Stairs in Python & JavaScript?

Is Climbing Stairs an easy or hard interview question?