Best Time to Buy and Sell Stock with Transaction Fee - Solution & Explanation
Problem Statement
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:
- You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
- The transaction fee is only charged once for each stock purchase and sale.
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 * 104
Approach Overview
Problem 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 1: Dynamic Programming Approach
In this approach, we use Dynamic Programming to manage two states: whether you're holding a stock or not on each day. The goal is to maximize the profit by deciding to buy, sell, or hold at each step while accounting for the transaction fee.
States: We define two states: hold[i] which represents the maximum profit you can have on day i when holding a stock, and cash[i] which represents the maximum profit on day i when not holding a stock.
State Transitions: On each day, you can either buy a stock (thus moving from cash[i-1] to hold[i]) or sell a stock (thus moving from hold[i-1] to cash[i]). Decisions should include transaction fee accordingly.
The C solution uses two variables, cash and hold, to keep track of the two states we have defined. Initially, cash is set to 0 (since you start with no money from stock), and hold is set to -prices[0] (representing buying a stock on the first day).
For each day, update cash with the maximum of not selling today or selling the stock today with added profit minus fee. Similarly, hold is updated with the maximum of not buying today or buying today by using available cash.
Complexity
Time Complexity: O(N), where N is the number of days, since we go through the prices once.
Space Complexity: O(1), as we use a fixed amount of extra space regardless of input size.
Approach 2: Greedy Approach
The greedy approach is an alternative solution that strives to maximize the profit by considering local optimal decisions. Unlike the dynamic approach that tracks two states, this method attempts to buy on dips and sell at peaks whenever possible while covering the transaction fee.
Keep track of the lowest price at which a stock might have been bought, and compare future prices to decide if selling should occur, adjusting the buy price to be less the transaction fee.
This C solution attempts to execute transactions only when it's profitable. It tracks the current minimum price known, and if selling would provide profit after fees, it moves to secure it by updating maxProfit. The minPrice is adjusted post-sale to ensure compliance with transaction costs.
Complexity
Time Complexity: O(N), since it processes each price once.
Space Complexity: O(1), using a constant set of additional variables.
Approach 3: Memoization
We design a function dfs(i, j), which represents the maximum profit that can be obtained starting from day i with state j. Here, j can take the values 0 and 1, representing not holding and holding a stock, respectively. The answer is dfs(0, 0).
The execution logic of the function dfs(i, j) is as follows:
If i geq n, there are no more stocks to trade, so we return 0.
Otherwise, we can choose not to trade, in which case dfs(i, j) = dfs(i + 1, j). We can also choose to trade stocks. If j \gt 0, it means that we currently hold a stock and can sell it. In this case, dfs(i, j) = prices[i] + dfs(i + 1, 0) - fee. If j = 0, it means that we currently do not hold a stock and can buy one. In this case, dfs(i, j) = -prices[i] + dfs(i + 1, 1). We take the maximum value as the return value of the function dfs(i, j).
The answer is dfs(0, 0).
To avoid redundant calculations, we use memoization to record the return value of dfs(i, j) in an array f. If f[i][j] is not equal to -1, it means that we have already calculated it, so we can directly return f[i][j].
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array prices.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Dynamic Programming
We define f[i][j] as the maximum profit that can be obtained up to day i with state j. Here, j can take the values 0 and 1, representing not holding and holding a stock, respectively. We initialize f[0][0] = 0 and f[0][1] = -prices[0].
When i geq 1, if we do not hold a stock at the current day, then f[i][0] can be obtained by transitioning from f[i - 1][0] and f[i - 1][1] + prices[i] - fee, i.e., f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i] - fee). If we hold a stock at the current day, then f[i][1] can be obtained by transitioning from f[i - 1][1] and f[i - 1][0] - prices[i], i.e., f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i]). The final answer is f[n - 1][0].
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array prices.
We notice that the transition of the state f[i][] only depends on f[i - 1][] and f[i - 2][]. Therefore, we can use two variables f_0 and f_1 to replace the array f, reducing the space complexity to O(1).
Code
Python
Java
C++
Go
TypeScript
Approach 5: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(N), where N is the number of days, since we go through the prices once. Space Complexity: O(1), as we use a fixed amount of extra space regardless of input size. |
| Greedy Approach | Time Complexity: O(N), since it processes each price once. Space Complexity: O(1), using a constant set of additional variables. |
| Memoization | — |
| Dynamic Programming | — |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
DP 40. Buy and Sell Stocks With Transaction Fee | Recursion to Space Optimisation • take U forward • 131,504 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Best Time to Buy and Sell Stock with Transaction Fee easy or hard?
Best Time to Buy and Sell Stock with Transaction Fee Python/Java solution
How to solve Best Time to Buy and Sell Stock with Transaction Fee in O(n)?
What is the best approach for Best Time to Buy and Sell Stock with Transaction Fee?
Is Best Time to Buy and Sell Stock with Transaction Fee asked at Google/Amazon/Meta?
What data structure is used in Best Time to Buy and Sell Stock with Transaction Fee?
What is the time complexity of Best Time to Buy and Sell Stock with Transaction Fee?
Ready to solve this problem?
Practice Best Time to Buy and Sell Stock with Transaction Fee with our built-in code editor and test cases.
Practice on FleetCode