Stock Transaction Fee LeetCode 714 Guide

LeetCode 714 Best Time to Buy and Sell Stock with Transaction Fee gives you an integer array prices where prices[i] is the price of a given stock on day i, and an integer fee representing a transaction fee per trade. You may complete as many transactions as you like — buy and sell repeatedly — but you must pay the fee each time you sell. You may not hold more than one share at a time. Maximize total profit.

The fee fundamentally changes the strategy compared to LeetCode 122 (Stock II, unlimited transactions, no fee). Without a fee, you greedily take every upward movement. With a fee, small upward movements may not be worth taking. A trade is only worthwhile if the selling price minus the buying price exceeds the fee. The DP state machine handles this automatically without any explicit greedy reasoning.

The problem sits at the intersection of greedy and dynamic programming thinking. While a pure greedy approach becomes complicated with fees, the DP state machine elegantly encodes the optimal decision at each day by tracking just two values: how much money you have when you are not holding stock, and how much effective cash you have when you are holding stock.

The state machine has exactly two states: cash (you are not holding any stock) and hold (you are holding one share). You initialize cash = 0 (you start with zero profit and no stock) and hold = -prices[0] (on day 0, if you buy, your effective cash position is -prices[0]). Then for each subsequent day, you update both states simultaneously.

The two recurrences are: cash = max(cash, hold + prices[i] - fee) and hold = max(hold, cash - prices[i]). The first equation says: on day i, you either do nothing (stay in cash state) or you sell at prices[i] and pay the fee (transition from hold to cash). The second equation says: on day i, you either do nothing (stay in hold state) or you buy at prices[i] (transition from cash to hold).

After processing all days, the answer is cash — the maximum profit when you are not holding any stock. You never want to end holding stock because it means you paid for a share without recouping its value. The state machine requires only two variables and one pass through the prices array: O(n) time and O(1) space.

There are four possible actions on any given day, forming four transitions in the state machine. Cash-to-cash means you do nothing while not holding stock — your cash balance stays the same. Hold-to-cash means you sell: you receive prices[i] but pay the fee, so cash increases by prices[i] - fee. Cash-to-hold means you buy: you pay prices[i] from your effective cash, so hold = cash - prices[i]. Hold-to-hold means you do nothing while holding stock — your hold position stays the same.

The key design decision is where to subtract the fee. You can subtract it on sell (hold + prices[i] - fee) or equivalently on buy (cash - prices[i] - fee). The math is identical — only one fee per round trip regardless. Subtracting on sell is more intuitive because you pay when you take profit. Subtracting on buy also works but mentally feels like you pay upfront, which can confuse interview interviewers.

The simultaneous update is important: both cash and hold use the values from the previous day. If you update cash first and then use the updated cash to compute hold, you would allow buying and selling on the same day, which is not permitted. In practice, because both new values are computed from the old values before any overwrite, a simple sequential assignment works correctly in most implementations.

LeetCode 122 Stock II (unlimited transactions, no fee) is the direct predecessor to this problem. Without the fee, the recurrences become cash = max(cash, hold + prices[i]) and hold = max(hold, cash - prices[i]). This is equivalent to the greedy approach of summing every positive daily difference: any upward movement is worth capturing.

The fee changes the threshold for profitable trades. With fee f, a sell at price p from a buy at price b is profitable only if p - b > f. Small fluctuations below the fee are ignored by the DP automatically — the hold-to-cash transition will not update cash unless hold + prices[i] - fee exceeds the current cash. Trades that do not clear the fee threshold simply leave both states unchanged.

This automatic threshold behavior is what makes the DP state machine superior to a greedy approach for the fee variant. A greedy approach would need to reason about future prices to decide whether to sell now or hold for a bigger gain later. The DP does this implicitly by considering both options at every step and keeping the maximum.

Consider prices = [1, 3, 2, 8, 4, 9] and fee = 2. Initialize cash = 0, hold = -1 (bought on day 0 at price 1). Day 1 (price=3): hold+3-2=0 which equals cash=0, so cash stays 0; cash-3=-3 which is less than hold=-1, so hold stays -1. Day 2 (price=2): hold+2-2=-1 < cash=0, no sell; cash-2=-2 < hold=-1, no buy. Day 3 (price=8): hold+8-2=5 > cash=0, so cash=5; hold=max(-1, 5-8)=max(-1,-3)=-1.

Continuing from day 3 (cash=5, hold=-1). Day 4 (price=4): hold+4-2=1 < cash=5, no sell; cash-4=1 > hold=-1, so hold=1 (we bought at 4, having 5 cash, effective position 5-4=1). Day 5 (price=9): hold+9-2=8 > cash=5, so cash=8; hold=max(1, 5-9)=max(1,-4)=1. Final answer: cash = 8.

The optimal trades are buy at 1 and sell at 8 (profit = 8-1-2 = 5) and buy at 4 and sell at 9 (profit = 9-4-2 = 3), for a total profit of 8. We correctly skipped selling at day 1 (price=3, profit 3-1-2=0) and buying back at day 2 (price=2) because the DP held the position to capture the larger move to 8. The state machine discovered this optimal hold-through automatically.

Python implementation: def maxProfit(prices, fee): cash, hold = 0, -prices[0]; for price in prices[1:]: cash, hold = max(cash, hold+price-fee), max(hold, cash-price); return cash. The simultaneous assignment (cash, hold = ..., ...) on a single line ensures both new values are computed from the old values before either is overwritten. This is idiomatic Python for the state machine. O(n) time, O(1) space.

Java implementation: public int maxProfit(int[] prices, int fee) { int cash = 0, hold = -prices[0]; for (int i = 1; i < prices.length; i++) { int newCash = Math.max(cash, hold + prices[i] - fee); int newHold = Math.max(hold, cash - prices[i]); cash = newCash; hold = newHold; } return cash; }. In Java, the explicit temp variables newCash and newHold are necessary to avoid overwriting cash before computing the new hold. This is the same simultaneous update as Python, just written more explicitly.

Both implementations loop once through prices with constant work per step — O(n) time overall and O(1) space since only two integers are maintained. There is no DP array needed: the state machine replaces the full array with two running maximums. In an interview, sketch the state diagram first, write the two recurrences, then code the loop. Mention the simultaneous update requirement and where the fee is subtracted.

The buy-sell-stock family spans six LeetCode problems. Stock I (121) allows one transaction — hold can only transition from the initial state once. Stock II (122) allows unlimited transactions without a fee — the same state machine as 714 but without the fee subtraction. Stock III (123) allows at most two transactions — extend to four states: buy1, sell1, buy2, sell2. Stock IV (188) allows at most k transactions — generalize to 2k states or use a k-element array.

Stock with Cooldown (309) adds a one-day rest period after selling. The state machine gains a third state: cooldown (just sold, cannot buy tomorrow). Transitions become: cash = max(cash, cooldown + prices[i]); cooldown = hold + prices[i]; hold = max(hold, cash - prices[i]). Stock with Transaction Fee (714, this problem) is Stock II plus one line of subtraction. Understanding all six variants gives you a complete command of the stock DP family.

Beyond stocks, the state machine pattern applies broadly to DP problems where you alternate between two or more modes. House Robber (198) alternates between rob and skip states. Paint House (256) cycles through color states. The key insight is always the same: define the states, write the transitions, update simultaneously. The state machine is one of the most powerful DP patterns for sequence problems where decisions have lasting state consequences.