Best Time to Buy and Sell Stock with Transaction Fee

Best Time to Buy and Sell Stock with Transaction Fee

What is this problem about?

The "Best Time to Buy and Sell Stock with Transaction Fee interview question" adds a "tax" to your trading. You can make as many transactions as you want, but every time you sell, you must pay a fixed transaction fee. This fee discourages frequent trading unless the profit from a specific transaction is large enough to cover the cost.

Why is this asked in interviews?

Citadel and Bloomberg ask the "Best Time to Buy and Sell Stock with Transaction Fee coding problem" to see if a candidate can adapt a greedy mindset to include costs. It tests whether you can identify that a transaction is only "worth it" if the price increase exceeds the fee. It is a fundamental test of "Dynamic Programming" and "Greedy" logic.

Algorithmic pattern used

This is solved using a Two-State Dynamic Programming approach.

1. hold[i]: Max profit on day $i$ if you currently own a stock.
   • hold[i] = max(hold[i-1], free[i-1] - prices[i])
2. free[i]: Max profit on day $i$ if you do not own a stock.
   • free[i] = max(free[i-1], hold[i-1] + prices[i] - fee) Notice that the fee is subtracted only when selling. Alternatively, you can subtract it when buying.

Example explanation

Prices: [1, 3, 2, 8, 4, 9], Fee: 2

• Day 1 (1): hold = -1, free = 0.
• Day 2 (3): free = max(0, -1 + 3 - 2) = 0. (No gain after fee).
• Day 4 (8): free = max(0, -1 + 8 - 2) = 5.
• Day 5 (4): hold = max(-1, 5 - 4) = 1. (Better to "reset" the buy at price 4).
• Day 6 (9): free = max(5, 1 + 9 - 2) = 8. Max Profit: 8.

Common mistakes candidates make

• Greedy ignoring the fee: Simply summing all prices[i] - prices[i-1] (like Stock II) and then subtracting the fee at the very end.
• Fee location: Subtracting the fee multiple times for the same transaction or forgetting to subtract it entirely.
• Memory usage: Using an $O(N)$ array when only the previous day's hold and free values are needed ($O(1)$ space).

Interview preparation tip

Cost-based optimization problems are common in fintech. Practice reducing space complexity by observing that you only need the previous state. This "Array interview pattern" optimization is always a bonus in the eyes of an interviewer.