The O(n) Club: Best Time to Buy and Sell Stock with a Transaction Fee (Or, How to Not Get Fleeced by the Middleman)

The O(n) Club: Best Time to Buy and Sell Stock with a Transaction Fee (Or, How to Not Get Fleeced by the Middleman)

⚡ TL;DR

Maximize stock trading profit, but with a catch: every time you sell, Wall Street’s favorite troll (the transaction fee) takes a bite. Forget brute force unless you enjoy time travel. Solution: track your life in two states—one where you hold a stock, one where you don’t. Update daily, profit maximally, and never confuse when to hand your money over to the bouncer.

// Java quickstart
int cash = 0, hold = -prices[0];
for (int i = 1; i < prices.length; i++) {
    cash = Math.max(cash, hold + prices[i] - fee);
    hold = Math.max(hold, cash - prices[i]);
}
return cash;

🧠 How Devs Usually Mess This Up

Look, I get it. You see “profits!” and want to buy low, sell high, rinse, repeat. But if you grab every opportunity without watching the transaction fee, you’ll leak more cash than a rusted pipe. Rookie mistakes include:

• Panic-selling every upswing (and paying the fee way too often)
• Applying the fee to both buy and sell—if you love misery, sure
• Trying to own twelve stocks at once (read the rules: only one stock at a time, future Gordon Gecko)

Trust me: greedy gets you ghosted by both profits and recruiters.

🔍 What’s Actually Going On

Let’s cook up an analogy: imagine you’re a chef and have to choose each morning—should you buy another sack of potatoes (stock) or just chill and stack your cash? Some days you sell your potatoes at the market (with a small booth fee: your transaction cost). Every day, you track:

• Cash state: What’s the biggest pile of cash you can have today not owning stock?
• Hold state: How much are you worth if you end today smugly clutching your one precious potato (stock)?

Every evening, update both: Sell if it’s worth it (minus fee), buy if the price is sweet, or just do nothing.

🛠️ PseudoCode

• Start with cash = 0 (pockets empty) and hold = -prices[0] (if you buy at dawn).
• Each day from day 1:
  • Sell? cash = max(cash, hold + prices[i] - fee); // Is it the right day to offload?
  • Buy? hold = max(hold, cash - prices[i]); // Or keep holding, or buy now
• At the end: return cash;

💻 The Code

// Java: Max Profit with Transaction Fee
public int maxProfit(int[] prices, int fee) {
    if (prices == null || prices.length == 0) return 0;
    int cash = 0;
    int hold = -prices[0];
    for (int i = 1; i < prices.length; i++) {
        int prevCash = cash;
        cash = Math.max(cash, hold + prices[i] - fee);
        hold = Math.max(hold, prevCash - prices[i]);
    }
    return cash;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Fee confusion: Only subtract fee on sale. Buying is weirdly free for once in your life.
• Double-selling: Don’t try to sell twice in a row. There are rules, even on Wall Street.
• Sad case #1: All prices go down. You get nothing. Welcome to crypto, 2022 edition.
• Time/space: One glorious sweep O(n), two variables O(1). That’s it, no matrix gymnastic required.

🧠 Interviewer Brain-Tattoo

“If greedy worked here, every trading bot would be retired on a beach. When in doubt, let DP keep your hands—and your profits—clean.”