The O(n) Club: Climbing Stairs Without Emptying Your Wallet (LeetCode 746)

The O(n) Club: Climbing Stairs Without Emptying Your Wallet (LeetCode 746)

⚡ TL;DR

The stairs want your money—but you’re smarter than that. You can step up one or two stairs at a time, pay the toll only when you land (not when you start), and your goal is to reach the top with your digital wallet (mostly) intact. Use dynamic programming. Here’s the Java shortcut:

public int minCostClimbingStairs(int[] cost) {
    int prev = 0, curr = 0;
    for (int i = 2; i <= cost.length; i++) {
        int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
        prev = curr;
        curr = next;
    }
    return curr;
}

🧠 How Devs Usually Mess This Up

Watch out for these classic banana peels:

• Paying at the wrong moment: You pay the cost when you land on a step, not when you leave it. Stop tipping empty stairs.
• Starting fee mix-up: Step 0 and step 1 are both legit starting spots—and both charge you nothing. Don’t accidentally pay before you blink.
• Finishing line confusion: The top is one past the last step, not the last step itself. No surprise curtain drops here. Don’t try to pay for an out-of-bounds stair.
• The brute-force trap: Recursion without memoization will nuke your performance on anything bigger than a toddler’s footstool. Save your CPU and your pride.

🔍 What’s Actually Going On

Picture a robot eyeing a staircase, every step with a random charge (and a bank account on life support). The robot can leap up 1 or 2 steps at any move—and only pays when landing. The destination is the top floor, which is not technically a step, but the honor of finishing. That means: avoid paying for fictional steps, and always look for the cheaper way to reach each stair, based on the prior two. Welcome to DP bootcamp.

The key is realizing you want the cheapest way to land atop the staircase. But since you can start at base 0 or 1 for free, the price is built up with each hop:

minCost(i) = min(minCost(i-1) + cost[i-1],
                minCost(i-2) + cost[i-2]);

Zero cost for step 0 and 1 means you’re basically walking into the gym, staring at the steps, and being told, “You haven’t broken a sweat yet. Go ahead.”

🛠️ PseudoCode

• Start with prev = 0, curr = 0.
  Spoiler: your cost to arrive at ‘ground’ and ‘step 1’ is nothing.
• For i from 2 to cost.length (inclusive):
  You want to “arrive” just above the top step (think: leaping onto the landing).
• For each i, set next = min(curr + cost[i-1], prev + cost[i-2])
  – You could have come from below (i-1), or leapt from two steps down (i-2).
• Update prev = curr; curr = next;
  – Only need two variables: low RAM, big bragging rights.
• Return curr;
  – That’s what it costs to walk into the afterparty.

💻 The Code

public int minCostClimbingStairs(int[] cost) {
    int prev = 0, curr = 0;
    for (int i = 2; i <= cost.length; i++) {
        int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
        prev = curr;
        curr = next;
    }
    return curr;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Small arrays? No sweat—even a one- or two-step staircase still works. If your answer looks like negative money, you probably started subtracting array bounds by accident.
• No cost at the finish line: Don’t try to pay cost[cost.length]—the landing is free, my friend.
• Exponential vs. linear: Brute force is O(2^n) sadness. This DP runs in O(n) time and uses O(1) extra memory. Save your RAM for Chrome tabs.

🧠 Interviewer Brain-Tattoo

“Dynamic Programming: Because future-you doesn’t want to redo math for every boring stair.”