Best Time to Buy and Sell Stock with Transaction Fee
Best Time to Buy and Sell Stock with Transaction Fee: max profit from unlimited trades where every completed transaction costs a flat fee.
- 1 <= prices.length <= 5 * 10⁴
- 1 <= prices[i] < 5 * 10⁴
- 0 <= fee < 5 * 10⁴
Intuition
Best time to buy and sell stock with transaction fee allows unlimited trades, but each completed sale costs a fixed fee. The fee changes the strategy fundamentally: capturing every small rise is no longer profitable, because a rise smaller than the fee loses money.
At the end of any day you are in one of two states — holding a share, or holding cash. Track the best possible balance in each:
- hold is the best balance while owning a share; cash is the best balance while owning none.
Each day, both states update from the previous day's values. hold is either unchanged or the result of buying today from yesterday's cash. cash is either unchanged or the result of selling today from yesterday's hold, minus the fee.
Charging the fee on the sale rather than the purchase is a convention, and the only rule is to apply it once per completed transaction — charging on both sides double-counts and produces answers that are too low.
Starting values matter: cash begins at 0 since no trade has happened, and hold begins at −prices[0], the balance after buying on day one.
The answer is the final cash. Ending while still holding a share is never better, because that share could have been sold — or never bought.
Notice that the fee is not compared against anything explicitly. The two-state recurrence handles the decision automatically: a rise too small to cover the fee simply never improves cash.
Two states, holding and free, with the fee charged once per completed transaction. Subtracting it on the sale rather than the purchase keeps the arithmetic in one place and makes the final answer read directly off free.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n) time and O(1) space.
Track two states per day
At each day's end you either hold a share or hold cash. hold is the best balance while owning a share, cash the best while owning none — two numbers describe the entire position.
Initialise both states
Set cash = 0, since no trade has occurred, and hold = -prices[0], the balance after buying on day one. Wrong starting values shift every subsequent day.
Update hold each day
hold = max(hold, cash - prices[i]) — either keep the current share or buy today using yesterday's cash. Buying does not incur the fee under this convention.
Update cash each day
cash = max(cash, hold + prices[i] - fee) — either stay out of the market or sell today. The fee is charged exactly once per completed transaction; charging on both sides double-counts.
Let the fee filter trades automatically
No explicit comparison against the fee is needed. A rise too small to cover it simply never improves cash, so the recurrence discards unprofitable trades on its own.
Return the final cash
The answer is cash after the last day. Ending while holding a share is never better — that share could have been sold, or never bought.
Cost of the scan
One pass over the prices with two variables updated per day gives O(n) time and O(1) space, with no array or table required.
Solution & live demo
Common pitfalls
Charging the fee twice
new_hold = max(hold, free - prices[i] - fee) new_free = max(free, hold + prices[i] - fee)
new_hold = max(hold, free - prices[i]) new_free = max(free, hold + prices[i] - fee)
A transaction is a buy and a sell, and the fee applies to the pair. Deducting on both halves doubles the cost and suppresses trades that are actually profitable.
Updating the states sequentially
hold = max(hold, free - prices[i]) free = max(free, hold + prices[i] - fee)
new_hold = ... new_free = ... hold, free = new_hold, new_free
The free line would use today's hold, letting a share be bought and sold within the same day for a guaranteed profit that isn't real. Both must read yesterday's values.
Returning the holding state
return max(hold, free)
return free
hold represents cash tied up in an unsold share and is always worse than having sold. The optimal plan never ends mid-position, so free is the answer by construction.
Edge cases
Every candidate sell value (hold + price - fee) stays below just staying free, so free never updates above 0 and the answer is 0.
hold becomes -prices[0] but free stays 0 since there is no second day to sell on; answer is 0.
The state machine naturally avoids paying the fee on every micro-uptick by only committing to a sell when hold + price - fee beats holding out for a later price.
Reduces exactly to the unlimited-transactions problem, since the sell transition becomes hold + price with no penalty.