Best Time to Buy and Sell Stock with Transaction Fee — State Machine DP with Cost

Problem Statement#

You are given an array prices where prices[i] is the price of a given stock on the i-th day and an integer fee representing a transaction fee. Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. Note: You may not engage in multiple transactions simultaneously.

Constraints:

• 1 <= prices.length <= 5 * 10^4
• 1 <= prices[i] < 5 * 10^4
• 0 <= fee < 5 * 10^4

Example 1:

Input:  prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation:
  Buy at price 1, sell at price 8: profit = 8 - 1 - 2 = 5.
  Buy at price 4, sell at price 9: profit = 9 - 4 - 2 = 3.
  Total = 5 + 3 = 8.

Example 2:

Input:  prices = [1, 3, 7, 5, 10, 3], fee = 3
Output: 6
Explanation: Buy at 1, sell at 7: profit = 7-1-3 = 3. Buy at 5, sell at 10: profit = 10-5-3 = 2. Total = 5.
             Or: Buy at 1, sell at 10: profit = 10-1-3 = 6. (Better.)

Example 3:

Input:  prices = [1, 3, 2, 8, 4, 9], fee = 5
Output: 3
Explanation: Buy at 1, sell at 9: profit = 9-1-5 = 3. Other transactions lose money after fee.

Why This Problem Matters#

Stock with Transaction Fee (LC 714) is the final entry in the stock problem series. It completes the picture: unlimited transactions (Stock II) but with a fee that discourages frequent trading.

The structural change is minimal — exactly one modification to the Stock II state machine: subtract fee from the sell transition. But the conceptual impact is significant. The fee changes the problem from "collect every upward slope" (Stock II greedy) to "collect only slopes that exceed the fee" — a fundamentally different selection problem that the greedy cannot solve directly.

This problem is also an excellent interview question for testing whether candidates understand the modular nature of state machine DP. The state transitions are a framework: constraints like fees, cooldowns, and transaction limits each modify exactly one transition, and they can be composed.

The Core Insight#

State machine (2 states):

• hold: Best profit achievable while holding a stock
• cash: Best profit achievable while not holding a stock

Transitions:

hold = max(hold, cash - price)    # keep holding, or buy today
cash = max(cash, hold + price - fee)  # rest, or sell today (pay fee)

This is identical to Stock II (hold = max(hold, cash - price) and cash = max(cash, hold + price)) with fee subtracted in the sell transition.

Why applying the fee at sell (not buy) is cleaner: The fee is paid per completed transaction. Applying it at the sell step is equivalent to applying it at the buy step (hold = max(hold, cash - price - fee) and cash = max(cash, hold + price)). Both are correct — just a matter of where the fee is charged. Sell-side is more intuitive ("you pay when you complete the transaction").

Base cases:

• hold = -infinity (haven't bought yet)
• cash = 0 (no transactions yet — profit is 0)

Answer: cash after all days.

Intuition for why the fee discourages frequent trades: With a fee of 2, a trade that makes profit 1 actually loses 1 after the fee. The state machine naturally skips trades where price - buy_price < fee because the sell transition would produce a cash value lower than the current cash — and max ensures we never take a loss.

Building the DP Solution#

Why Stock II greedy fails with a fee: Stock II greedy collects every upward adjacent slope: sum(max(p[i]-p[i-1], 0)). With a fee, summing many tiny upward slopes leads to paying the fee repeatedly — worse than holding through the whole move. The greedy breaks.

Example: prices = [1, 2, 3, 4, 5], fee = 2. Greedy sum = (2-1)+(3-2)+(4-3)+(5-4) = 4. Fee paid 4 times = 8 total fees, net profit = 4 - 8 = -4. Obviously wrong.

State machine gives: hold at 1, sell at 5, profit = 5-1-2 = 2. Correct.

State machine implementation:

def maxProfit(prices, fee):
    hold = float('-inf')
    cash = 0
    for price in prices:
        hold = max(hold, cash - price)         # buy using current cash
        cash = max(cash, hold + price - fee)   # sell and pay fee
    return cash

Visual Dry Run#

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2

Answer: cash = 8

Optimal trades:

• Buy day 1 (price=1), sell day 4 (price=8): profit = 8-1-2 = 5
• Buy day 5 (price=4), sell day 6 (price=9): profit = 9-4-2 = 3
• Total = 8

Note how the state machine considers buying on day 5 using the cash = 5 from the previous sell. hold on day 5 = 5 - 4 = 1, representing profit from carrying forward after the first sell and buying again.

Optimized Solution#

Python#

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        # hold = best profit while holding a stock
        # cash = best profit while NOT holding a stock
        hold = float('-inf')  # haven't bought yet
        cash = 0              # no transactions yet
 
        for price in prices:
            prev_hold = hold
            # Buy today using current cash, or keep holding
            hold = max(hold, cash - price)
            # Sell today (pay fee), or rest — use prev_hold to avoid same-day buy-sell confusion
            cash = max(cash, prev_hold + price - fee)
 
        return cash

JavaScript#

var maxProfit = function(prices, fee) {
    let hold = -Infinity;
    let cash = 0;
 
    for (const price of prices) {
        const prevHold = hold;
        hold = Math.max(hold, cash - price);       // buy or keep holding
        cash = Math.max(cash, prevHold + price - fee); // sell (with fee) or rest
    }
 
    return cash;
};

Note: Using prev_hold in the cash update avoids potential same-day buy-sell at the same price affecting results (since profit would be -fee, which is always negative, max prevents it anyway — but using prev_hold is cleaner).

Complexity Analysis#

Common Mistakes#

1. Using the Stock II greedy (collecting every upward slope). With fees, collecting every small upward movement repeatedly pays fees and is usually suboptimal. The state machine is required.

2. Subtracting the fee twice (once on buy, once on sell). Choose one side to charge the fee — typically the sell side. If you subtract fee/2 from both sides, you get wrong results for odd fees. Pick sell side: cash = max(cash, hold + price - fee).

3. Not snapshotting hold before updating it. The Python version above saves prev_hold = hold before updating hold. If you don't, then cash = max(cash, hold + price - fee) uses the just-updated hold (same-day buy profit used for same-day sell). While max prevents a net loss, using prev_hold is conceptually correct.

4. Returning hold instead of cash. At the end, the maximum profit when not holding any stock is cash. hold still contains the value of an unsold position — never return it as the final answer.

5. Confusing the fee direction. "Fee per transaction" means one fee per complete buy-sell cycle. If you charge the fee at buy, the buy transition becomes hold = max(hold, cash - price - fee) and sell is unchanged. Either is correct — but mixing both (fee at buy AND sell) doubles the fee.

Interview Tips#

• Immediately connect to Stock II: "This is Stock II with one modification: subtract fee from the sell transition. The framework is identical."
• Explain why greedy breaks: "Stock II greedy collects every upward slope. With fees, collecting many tiny slopes means paying the fee many times — the state machine naturally avoids this by taking max before updating cash."
• Use prev_hold for clarity: "I'll snapshot hold before updating it to avoid any ambiguity about same-day buy-sell ordering."
• Show the fee placement is a choice: "I could charge the fee on buy (hold = max(hold, cash - price - fee)) — mathematically equivalent. I prefer sell-side since that's when the transaction completes."

Follow-up Questions#

Q: What if fees are charged per stock held per day (holding cost)? The sell transition stays the same, but the hold transition changes: hold = max(hold - daily_fee, cash - price) — each day you hold, you pay. This is a more complex variant rarely asked.

Q: What if there is both a transaction fee and a 1-day cooldown? Combine both constraints: use the 3-state cooldown machine (holding, sold, resting) and subtract fee in the sold = holding + price - fee transition.

Q: How large can the fee be before no transaction is profitable? If fee >= max(prices) - min(prices) for any subarray, no transaction is profitable. But computing this analytically is complex — the state machine handles it implicitly via max.

Q: Can this be solved with the greedy approach if fees are small? No. The greedy can never correctly account for fees because it doesn't know in advance which slopes to combine into multi-day trades. The state machine always gives the correct answer regardless of fee size.

Key Takeaways#

• Stock with Fee = Stock II state machine + subtract fee in the sell transition.
• hold = max(hold, cash - price) and cash = max(cash, hold + price - fee).
• The Stock II greedy (collect every upward slope) is WRONG here — fees make many small trades suboptimal.
• The state machine naturally avoids unprofitable trades: if selling produces a value less than the current cash, max ignores the sell.
• Fee can be charged at buy or sell — not both. Choose sell-side for clarity.
• This is the modular beauty of state machine DP: cooldown modifies the buy transition, fees modify the sell transition, and both can be composed independently.
• Amazon, Google, and Meta use this as the "closing question" in stock series interviews to verify understanding of the framework, not just memorization.