The O(n) Club: Best Time to Buy and Sell Stock III: Survive the Two-Trade Gauntlet

The O(n) Club: Best Time to Buy and Sell Stock III — Survive the Two-Trade Gauntlet

⚡ TL;DR

Buy, sell, buy, sell—can you time these two trades for max profit on an array of stock prices? Brute force brings pain. Four variables bring glory:

// Java glow-up
int firstBuy = Integer.MIN_VALUE, firstSell = 0;
int secondBuy = Integer.MIN_VALUE, secondSell = 0;
for (int price : prices) {
    firstBuy = Math.max(firstBuy, -price);
    firstSell = Math.max(firstSell, firstBuy + price);
    secondBuy = Math.max(secondBuy, firstSell - price);
    secondSell = Math.max(secondSell, secondBuy + price);
}
return secondSell;

🧠 How Devs Usually Mess This Up

It’s almost a rite of passage to cook up two nested for-loops, split the timeline at every possible point, and hope the interviewer loves O(n²) solutions. They don’t. Or maybe you try the single-trade code twice and assume real life is just a bunch of copy-paste. Yeah, if only money worked that way.

🔍 What’s Actually Going On

Your profit is a wallet with separation anxiety. Each buy takes money out, each sell puts some back. Two trades, so two chances to fumble. Instead of tracking every possible trade combo, keep four evolving “states”:

🛠️ PseudoCode

• firstBuy = lowest (most negative) balance after buying anytime so far: firstBuy = max(firstBuy, -price)
• firstSell = max cash after selling first: firstSell = max(firstSell, firstBuy + price)
• secondBuy = max after buying again (spending your winnings): secondBuy = max(secondBuy, firstSell - price)
• secondSell = ultimate loot after final sell: secondSell = max(secondSell, secondBuy + price)

• Loop once through prices updating each as you go.
• Return secondSell. (If you never bought, congrats: zero profit, zero risk—still broke.)

💻 The Code

public int maxProfit(int[] prices) {
    int firstBuy = Integer.MIN_VALUE, firstSell = 0;
    int secondBuy = Integer.MIN_VALUE, secondSell = 0;
    for (int price : prices) {
        firstBuy = Math.max(firstBuy, -price);
        firstSell = Math.max(firstSell, firstBuy + price);
        secondBuy = Math.max(secondBuy, firstSell - price);
        secondSell = Math.max(secondSell, secondBuy + price);
    }
    return secondSell;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Zero or One Price? Sorry, no lottery—and not even a contest. No buys = no gains.
• Buy After You Sell: Thanks to update order, you never buy #2 before you’ve sold #1.
• Sign Sabotage: Forget a minus and it’s game over—your wallet grows suspiciously fast in the wrong direction.
• Space/Time: O(n) time, O(1) memory. Less data than your Spotify playlist, more profit than your weekend gig economy hustle.

🧠 Interviewer Brain-Tattoo

“You can chain two profits with four lines and no extra arrays. If you go quadratic in 2024, invest in a time machine, not stocks.”