You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top? This is essentially Fibonacci: ways(n) = ways(n-1) + ways(n-2). You can reach step n from step n-1 (take 1 step) or from step n-2 (take 2 steps). Only two variables needed — O(1) space.

The step-through player is coming for this one. Two Sum has the full animation today; the rest are being authored in the admin.

Pythontime O(n) · space O(1)

def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

Next upValid Anagram

Two Sum is free. Enroll to unlock every visualization and save where you stopped.Enroll free

Watch the video walkthrough