#714 Best Time to Buy and Sell Stock with Transaction Fee
the problem
In plain words
prices[i] is a stock's price on day i, and every completed trade (one buy plus the sell that closes it) costs a fixed fee. You may trade any number of times but hold at most one share at a time. Return the largest total profit after paying all fees.
in prices = [1,3,2,8,4,9], fee = 2
out 8
Buy at 1, sell at 8 (7 − 2 = 5); buy at 4, sell at 9 (5 − 2 = 3).
in prices = [1,3,7,5,10,3], fee = 3
out 6
- 1 ≤ prices.length ≤ 5·10⁴
- 1 ≤ prices[i] < 5·10⁴
- 0 ≤ fee < 5·10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternState-machine DP
Two modes are enough: CASH (no share) and HOLD (one share). The fee rides on the sell arrow, so a small dip is no longer worth a sell and a rebuy — the DP decides that for you.
solutions
From brute force to optimal
best(day, holding): rest, or buy (if empty-handed), or sell and pay the fee (if holding).
- Past the last day → 0.
- rest = best(day + 1, holding).
- Holding: price − fee + best(day + 1, false). Not holding: −price + best(day + 1, true).
- Return the larger.
Two choices per day, nothing cached.
Recursion depth n.
class Solution { public int maxProfit(int[] prices, int fee) { return best(prices, fee, 0, false); } /** Best profit from day i to the end, given whether we hold a share right now. */ private int best(int[] prices, int fee, int i, boolean holding) { if (i == prices.length) return 0; int rest = best(prices, fee, i + 1, holding); // do nothing today int act = holding ? prices[i] - fee + best(prices, fee, i + 1, false) // sell and pay the fee : -prices[i] + best(prices, fee, i + 1, true); // buy return Math.max(rest, act); }}2n states; cache each answer.
- int[n][2] memo, −1 = unknown.
- Check, compute, store.
2n states × O(1).
Memo + recursion depth.
class Solution { public int maxProfit(int[] prices, int fee) { int[][] memo = new int[prices.length][2]; // -1 = unknown (answers are never negative) for (int[] row : memo) Arrays.fill(row, -1); return best(prices, fee, 0, 0, memo); } private int best(int[] prices, int fee, int i, int holding, int[][] memo) { if (i == prices.length) return 0; if (memo[i][holding] != -1) return memo[i][holding]; int rest = best(prices, fee, i + 1, holding, memo); int act = holding == 1 ? prices[i] - fee + best(prices, fee, i + 1, 0, memo) : -prices[i] + best(prices, fee, i + 1, 1, memo); return memo[i][holding] = Math.max(rest, act); }}cash = best profit with no share, hold = best with one share; update both from yesterday's pair.
- cash = 0, hold = −prices[0].
- newCash = max(cash, hold + p − fee); newHold = max(hold, cash − p).
- Assign both; return cash.
One pass, two max() per day.
Four ints.
class Solution { public int maxProfit(int[] prices, int fee) { int cash = 0; // best profit holding nothing int hold = -prices[0]; // best profit holding one share (bought on day 0) for (int i = 1; i < prices.length; i++) { int p = prices[i]; int newCash = Math.max(cash, hold + p - fee); // stay out, or sell and pay the fee int newHold = Math.max(hold, cash - p); // keep holding, or buy with yesterday's cash cash = newCash; hold = newHold; } return cash; }}Cash and hold, with the fee on the sell arrow
in the room
How to say it in the interview
talk track
- "This is LC 122's cash/hold DP with one change: subtract the fee when selling."
- Explain why LC 122's greedy (add every rise) breaks: each separate trade pays the fee, so holding through a small dip can beat selling and rebuying.
- O(n) time, O(1) memory.
traps
- Charging the fee on both the buy and the sell — it is once per completed trade.
- Trading every valley-to-peak run as in LC 122: each trade pays the fee. Example 1 has three runs, 2 + 6 + 5 − 3 × 2 = 7, but holding through the small 3 → 2 dip gives 8.
what they ask next
Follow-ups
Charge the fee on the buy instead?
Same answer: subtract it on the buy arrow, hold = max(hold, cash − p − fee).
A cooldown as well?
Use LC 309's three-state machine and subtract the fee on its sell arrow.
before you submit
Edge cases to test
- One day → 0.
- A rise smaller than the fee isn't worth a trade: [1,5] with fee 4 → 0.
- Fee 0 → the same answer as LC 122 (add every rise).
practise next
Similar problems
- #309Best Time to Buy and Sell Stock with CooldownMediumin DP Patterns
- #122Best Time to Buy and Sell Stock IIMediumin Arrays & Strings