Best time to buy and sell stock with transaction fees
MediumCharge the fee once per transaction
Problem
Maximize profit with unlimited transactions, paying a fee per transaction.
Track holding vs cash; every sale subtracts the fee, so only trade when it still pays off.
The idea
The unlimited-transaction two-state machine with the fee subtracted on either the buy or the sell — as long as it is charged exactly once per round trip. The fee is what stops profitably churning on tiny moves.
The trick
- Subtract the fee on the sell (or the buy), never both.
- O(n) time, O(1) space.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — prices=[1,3,2,8,4,9], fee=2 Values: 1, 3, 2, 8, 4, 9.
1cash=0; hold=-p[0]2for p: cash=max(cash,hold+p-fee); hold=max(hold,cash-p)Input
- array
- [1, 3, 2, 8, 4, 9]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- prices = [1, 3, 2, 8, 4, 9], fee = 2
- Output:
- 8
- Explanation:
- Best profit after fees is 8.
Example 2
- Input:
- prices = [1, 3, 7, 5, 10, 3], fee = 3
- Output:
- 6
- Explanation:
- Careful trades net 6.
Example 3
- Input:
- prices = [1, 1, 1], fee = 1
- Output:
- 0
- Explanation:
- Fee eats any profit → 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.