Best Time to Buy and Sell Stock with Transaction Fee
Max profit from unlimited trades where every completed transaction costs a flat fee.
Open on LeetCode ↗Intuition
The instinctive move is to subtract the fee whenever money changes hands, once on the buy and once on the sell. That double-charges every round trip and undercounts profit. The fee is per completed transaction, not per action, so charge it exactly once, conventionally when you sell, and leave the buy transition untouched. Once that's settled, this is otherwise the same two-state recurrence as unlimited-transaction stock trading: hold a share or be free of one, each a running max over what you did yesterday.
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
Two rolling states
hold tracks the best profit while owning a share; free tracks the best profit owning nothing. Initialize hold to -prices[0] (buy immediately) and free to 0.
Charge the fee once, on the sell
Each day, new_hold is the better of keeping yesterday's share or buying today out of yesterday's free. new_free is the better of staying free or selling today's held share, subtracting the fee only on that sell transition: hold + price - fee.
Answer is the final free state
Ending the timeline while still holding a share can never be optimal, since selling it (even after paying the fee) is only ever better or equal. The answer is free after the last day.
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.