The O(n) Club: Best Time to Buy and Sell Stock: Because Margins and Caffeine Can Only Do So Much

The O(n) Club: Best Time to Buy and Sell Stock: Because Margins and Caffeine Can Only Do So Much

⚡ TL;DR

One shot at glory: buy low, sell high. You only get one transaction, so don’t get greedy. Walk through the prices, keep track of the cheapest buy, and snag the biggest profit possible—even if you code like you’re double-parked.

// Java one-pass wonder
int min = Integer.MAX_VALUE;
int maxProfit = 0;
for (int p : prices) {
    if (p < min) min = p;
    if (p - min > maxProfit) maxProfit = p - min;
}
return maxProfit;

🧠 How Devs Usually Mess This Up

Let’s face it: most devs approach this problem like they’re prepping for Y2K. First instinct? Brute-force it with double for-loops—every buy day, every possible sell day. It’s O(n²) in runtime and O(n²) on your sanity. Some will try to buy and sell on the same day (sure, you get your money back, congrats). And the bold ones? They rewrite it as if you can buy and sell as often as your Git rebase strategy. Nice try. Not this time.

🔍 What’s Actually Going On

Imagine walking through a town market with a clipboard: each stall shouts a price, and you scribble down the best deal so far. Every new stall, you quickly check: if I bought at my lowest so far, how much would I make if I sold right here? If that margin beats all previous scores, new high score! No crystal ball. No double-backs. It’s a left-to-right game—a true single-pass, low-stress move even your sleep-deprived manager can explain at standup.

🛠️ PseudoCode

• Set minPrice to Integer.MAX_VALUE. Just assume a price so high, even Web3 marketers would blush.
• Set maxProfit to 0, because at this point, the best you’ve done is lose time.
• For every price in your input:
  • If price < minPrice, update minPrice (“Breaking news: Prices CAN go lower!”)
  • Else, check if price - minPrice beats your maxProfit
  • If so, bless yourself with a new maxProfit
• After the stroll, return maxProfit, even if it’s zero (some markets are just… bad).

// Pseudo-Java
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
    if (price < minPrice) minPrice = price;
    else if (price - minPrice > maxProfit) maxProfit = price - minPrice;
}
return maxProfit;

💻 The Code

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;
    for (int price : prices) {
        if (price < minPrice) {
            minPrice = price; // Found a cheaper buy
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice; // Best profit so far
        }
    }
    return maxProfit; // 0 if you’re cursed by the market
}

⚠️ Pitfalls, Traps & Runtime Smacks

• All prices dropping? Just return 0. You can’t short stocks here—this isn’t a Wall Street movie.
• Thinking buy and sell can happen on the same day? Sorry, but that’s just a no-op. Save your button clicks.
• Empty or single-entry array? That’s not a trading week, that’s an existential crisis. Still: method returns 0.
• Performance: Thanks to our one walk-through, time is O(n) and space is O(1). Less memory than your last snack break.

🧠 Interviewer Brain-Tattoo

“You’re not paid for complicated solutions; you’re paid for solutions that work before your coffee goes cold.”