Watch 10 video solutions for Best Time to Buy and Sell Stock with Transaction Fee, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by Algorithms Made Easy has 12,598 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.
Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.
Note:
Example 1:
Input: prices = [1,3,2,8,4,9], fee = 2 Output: 8 Explanation: The maximum profit can be achieved by: - Buying at prices[0] = 1 - Selling at prices[3] = 8 - Buying at prices[4] = 4 - Selling at prices[5] = 9 The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3 Output: 6
Constraints:
1 <= prices.length <= 5 * 1041 <= prices[i] < 5 * 1040 <= fee < 5 * 104Problem Overview: You receive an array prices where prices[i] is the stock price on day i, and a transaction fee applied to every sale. You can buy and sell multiple times, but you must sell before buying again. The goal is to maximize total profit while accounting for the fee.
Approach 1: Dynamic Programming (O(n) time, O(1) space)
This problem fits naturally into dynamic programming. Track two states while iterating through the array: hold (maximum profit if you currently own a stock) and cash (maximum profit if you do not own a stock). For each price, update these states using transitions: buying moves from cash to hold, and selling moves from hold to cash while subtracting the transaction fee. The key insight is that you only care about the best profit in these two states at each step, so a full DP table is unnecessary. Iterating once through the prices updates the states in constant space.
Approach 2: Greedy Strategy (O(n) time, O(1) space)
The greedy view observes that transaction fees effectively increase the cost of buying. Instead of explicitly modeling states, maintain an effective buying price that already includes the fee. While iterating through the array, update this cost when a cheaper opportunity appears. When the current price exceeds the effective cost, you lock in profit and adjust the buy price to reflect the transaction. This works because any profitable increase should be captured immediately once it covers the fee, ensuring you never miss cumulative gains from rising trends.
Recommended for interviews: The dynamic programming formulation is typically expected because it clearly expresses the state transitions (hold vs cash) and generalizes to other stock problems. Many interviewers like seeing this pattern because it appears across multiple variations such as cooldown or limited transactions. The greedy optimization is shorter and elegant once you recognize the fee adjustment trick, but demonstrating the DP reasoning first shows stronger problem‑solving fundamentals.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (hold/cash states) | O(n) | O(1) | General solution for stock trading problems with constraints like fees, cooldowns, or transaction limits |
| Greedy Profit Tracking | O(n) | O(1) | When you recognize the fee-adjusted buy price trick and want the most concise optimal solution |