The O(n) Club: Climbing Stairs — Fibonacci, But With Calves of Steel

The O(n) Club: Climbing Stairs — Fibonacci, But With Calves of Steel

⚡ TL;DR

Climbing n stairs, taking 1 or 2 steps at a time? Congratulations, you’re reenacting the Fibonacci sequence at your local gym. Sure, you could awkwardly brute-force it with recursion and blow your stack, but why not impress your CPU with a slick O(1) space DP trick in Java?

// Java: The stair master version
public int climbStairs(int n) {
    int a = 1, b = 1;
    for (int i = 2; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

🧠 How Devs Usually Mess This Up

The classics:

🔍 What’s Actually Going On

Imagine you’re climbing: to reach step n, you either leapt from n-1 or double-jumped from n-2. Every path is a remix of those two moves. If you spot this is just the Fibonacci sequence with a gym flavor, you win. Best part: you only need to remember how you got to the last two stairs—leave the rest of the history to historians and your browser cache.

🛠️ PseudoCode

• Base cases? If n == 0 or 1, return 1. Even lazy people get to the door.
• Initialize two trackers: Both start at 1 (ways to stand still and ways to reach the first step, because let’s not overthink it).
• For i = 2; i <= n; ++i:
  • current = a + b;
  • Shift those calves: a = b, b = current;
• Return b; You’ve climbed Mt. Fibonacci and lived to tell the tale.

💻 The Code

public int climbStairs(int n) {
    if (n == 0 || n == 1) return 1;
    int a = 1, b = 1;
    for (int i = 2; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Naive recursion? Works fine for baby stairs, cries for n > 30.
• Wasting arrays? Unless you want every intermediary number (which you don’t—trust me), skip the space bloat.
• Negative stairs? No. Just no.
• Don’t code-golf yourself out of a job: Readable beats clever when you’re debugging with 2% battery left.
• Runtime: O(n) time, O(1) space—your RAM and interviewer will both thank you.

🧠 Interviewer Brain-Tattoo

“If it smells like recursion and looks like Fibonacci—it probably wants O(1) space and a coffee.”