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

You can buy and sell a stock as many times as you like, but every time you complete a round trip (buy then sell), you pay a flat transaction fee. That single constraint changes the problem significantly. Without the fee, you collect every upward price move greedily. With the fee, some of those small gains are not worth the cost. You need to be more selective about which trades to take.

This is LeetCode 714: Best Time to Buy and Sell Stock with Transaction Fee, a medium problem that builds on the unlimited-transactions version (LeetCode 122). The solution uses a two-state DP approach that runs in O(n) time and O(1) space.

The problem

Given an array prices where prices[i] is the price of a stock on day i, 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 fee for each transaction (one buy and one sell counts as a single transaction).

prices = [1, 3, 2, 8, 4, 9], fee = 2  -> 8

The approach

The key insight is to model the problem as a state machine with two states: cash (you are not holding any stock) and hold (you currently own one share).

At each day, you update both states:

• cash = max(cash, hold + price - fee): either stay in cash, or sell the stock you are holding and pay the fee.
• hold = max(hold, cash - price): either keep holding, or buy at today's price using your current cash.

The cash state starts at 0 because you begin with no stock and no profit. The hold state starts at -prices[0] because buying on day 0 costs you that amount.

This formulation naturally handles the fee. Every time you sell (transitioning from hold to cash), you subtract the fee. Small price bumps that do not cover the fee get filtered out by the max operation.

The solution

def maxProfit(prices, fee):
    cash = 0
    hold = -prices[0]

    for i in range(1, len(prices)):
        cash = max(cash, hold + prices[i] - fee)
        hold = max(hold, cash - prices[i])

    return cash

Here is what each piece does:

1. cash = 0: you start without holding stock and with zero profit.
2. hold = -prices[0]: if you buy on day 0, your "profit" so far is negative (you spent money).
3. For each subsequent day, you check whether selling improves cash and whether buying improves hold. The max keeps whichever option is better.
4. Return cash. The optimal answer always ends with no stock in hand, because holding stock at the end is never better than selling it.

Step-by-step walkthrough

Let's trace through prices = [1, 3, 2, 8, 4, 9] with fee = 2. At each day, we update cash and hold, then note which transition the algorithm chose.

The answer is 8. The algorithm found two profitable trades: buy at 1 and sell at 8 (net +5 after fee), then buy at 4 and sell at 9 (net +3 after fee). Trades like buying at 1 and selling at 3 were skipped because the +2 gain does not cover the fee of 2.

Complexity analysis

Time: O(n). You visit each price exactly once. Each visit does O(1) work: two comparisons and at most two updates.

Space: O(1). You use two variables (cash and hold) regardless of input size. No extra arrays, no hash maps, no recursion stack.

The building blocks

State machine DP

The state machine pattern is a powerful way to model problems where you transition between a fixed number of states on each step. For stock trading problems, the states represent whether you currently hold stock or not. Each transition has a cost or reward attached (buying costs money, selling earns money minus the fee).

This same pattern appears across the entire family of stock trading problems:

• LeetCode 121 (one transaction): two states, but you can only buy once and sell once.
• LeetCode 122 (unlimited, no fee): two states, same as this problem but with fee = 0.
• LeetCode 123 (at most two transactions): four states tracking two separate buy/sell cycles.
• LeetCode 309 (cooldown): three states, adding a "rest" state after selling.
• LeetCode 714 (this problem): two states with a fee deducted on each sell.

Once you internalize the two-state pattern (cash and hold), each variant just adds a small twist to the transition rules. The skeleton stays the same: loop through prices, update each state with a max of staying or transitioning.

Edge cases

Before submitting, make sure your solution handles these:

• Fee larger than any price difference: if no single trade covers the fee, the answer is 0. cash never gets updated past its initial value.
• Monotonically decreasing prices like [5, 4, 3, 2, 1]: no profitable trade exists even without a fee. Return 0.
• Monotonically increasing prices like [1, 2, 3, 4, 5] with fee = 0: one long hold equals the sum of all daily gains. The DP captures this because selling and re-buying on consecutive days with zero fee is equivalent to holding.
• Single element [5]: the loop body never executes. Return 0.
• Two elements [1, 5] with fee = 2: selling gives 5 - 1 - 2 = 2, which is positive. Return 2.

From understanding to recall

You have read through the two-state DP and it makes sense. cash and hold, updated with max at each step, fee subtracted on sell. But can you write it from scratch under time pressure without looking back?

The details matter: initializing hold to -prices[0], subtracting the fee in the cash update (not the hold update), and using the updated cash when computing hold. These are small choices that are easy to second-guess if you have not practiced writing them from memory.

Spaced repetition closes that gap. You write the two-state loop from scratch at increasing intervals until the code flows out automatically. After a few rounds, you see "stock trading with fee" and the state machine pattern triggers immediately.

The state machine DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Best Time to Buy and Sell Stock - The classic single-transaction version
• Best Time to Buy and Sell Stock II - Unlimited transactions without fee
• Best Time to Buy and Sell Stock with Cooldown - Similar state machine with cooldown instead of fee

CodeBricks breaks the stock trading with transaction fee problem into its state machine DP building block, then drills it independently with spaced repetition. You type the two-state transition from scratch until it is automatic. When a stock trading variant shows up in your interview, you do not hesitate. You just write it.