{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Climbing Stairs – Solution & Complexity

Interview solutions
/
Climbing Stairs
Quick practice for Climbing Stairs: 3 reasoning beats, no typing

Watch: Climbing Stairs with dynamic programming

To reach step n, your last move was from step n−1 or n−2, so ways(n) = ways(n−1) + ways(n−2): Fibonacci. Plain recursion repeats work exponentially; building up from the bottom with two variables is O(n) time and O(1) space.

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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

FAQ

See also

Practice Climbing Stairs online (run code in the browser)Fibonacci Number solution (easy)Unique Paths solution (medium)Add Two Numbers solution (medium)Best Time to Buy and Sell Stock solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?