Best Time to Buy and Sell Stock with Transaction Fee solution and explanation
Google
9 more videos on this problem
Best Time to Buy and Sell Stock with Transaction Fee | Live Coding with Explanation | Leetcode - 714Algorithms Made Easy · 9:09 · 12K views
LeetCode 714. Best Time to Buy and Sell Stock with Transaction FeeHappy Coding · 11:35 · 8K views
Leetcode - Best Time to Buy and Sell Stock with Transaction Fee (Python)Timothy H Chang · 2:44 · 5K views
LeetCode 714 Best Time to Buy and Sell Stock with Transaction FeeJeevan Kumar - Cracckify · 12:22 · 3K views
LeetCode Solutions | 714 | Best Time to Buy and Sell Stock with Transaction FeeRahul Manghnani · 8:49 · 2K views
Leetcode 714. Best Time to Buy and Sell Stock with Transaction FeeElite Code · 38:49 · 1K views
Daily Leetcode #1178: Jun 22, 2023 - 714. Best Time to Buy and Sell Stock with Transaction FeeProgramming Live with Larry · 6:20 · 1K views
Best Time to Buy and Sell Stock with Transaction Fee - LeetCode 714 - PythonAlpha-Code · 17:00 · 635 views
Daily Leetcode #350: Mar 16, 2021 - 714. Best Time to Buy and Sell Stock with Transaction FeeProgramming Live with Larry · 12:30 · 632 views
DP 40. Buy and Sell Stocks With Transaction Fee | Recursion to Space Optimisationtake U forward · 7:20 · 131K views
The problem
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.
class Solution:
def maxProfit(self, prices, fee):
cash, hold = 0, -prices[0]
for i in range(1, len(prices)):
cash = max(cash, hold + prices[i] - fee)
hold = max(hold, cash - prices[i])
return cash
if __name__ == "__main__":
sol = Solution()
prices = [1, 3, 2, 8, 4, 9]
fee = 2
print("Maximum profit:", sol.maxProfit(prices, fee))class Solution {
public int maxProfit(int[] prices, int fee) {
int cash = 0, hold = -prices[0];
for (int i = 1; i < prices.length; ++i) {
cash = Math.max(cash, hold + prices[i] - fee);
hold = Math.max(hold, cash - prices[i]);
}
return cash;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] prices = {1, 3, 2, 8, 4, 9};
int fee = 2;
System.out.println("Maximum profit: " + sol.maxProfit(prices, fee));
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int cash = 0, hold = -prices[0];
for (int i = 1; i < prices.size(); ++i) {
cash = max(cash, hold + prices[i] - fee);
hold = max(hold, cash - prices[i]);
}
return cash;
}
};
int main() {
vector<int> prices = {1, 3, 2, 8, 4, 9};
int fee = 2;
Solution sol;
int result = sol.maxProfit(prices, fee);
return 0;
}var maxProfit = function(prices, fee) {
let cash = 0, hold = -prices[0];
for (let i = 1; i < prices.length; i++) {
cash = Math.max(cash, hold + prices[i] - fee);
hold = Math.max(hold, cash - prices[i]);
}
return cash;
};
console.log(maxProfit([1, 3, 2, 8, 4, 9], 2));#include <stdio.h>
int maxProfit(int* prices, int pricesSize, int fee) {
if (pricesSize == 0) return 0;
int cash = 0;
int hold = -prices[0];
for (int i = 1; i < pricesSize; ++i) {
cash = (cash > hold + prices[i] - fee) ? cash : (hold + prices[i] - fee);
hold = (hold > cash - prices[i]) ? hold : (cash - prices[i]);
}
return cash;
}
int main() {
int prices[] = {1, 3, 2, 8, 4, 9};
int fee = 2;
printf("Maximum profit: %d", maxProfit(prices, 6, fee));
return 0;
}using System;
public class Solution {
public int MaxProfit(int[] prices, int fee) {
int cash = 0, hold = -prices[0];
for (int i = 1; i < prices.Length; ++i) {
cash = Math.Max(cash, hold + prices[i] - fee);
hold = Math.Max(hold, cash - prices[i]);
}
return cash;
}
public static void Main(string[] args) {
var sol = new Solution();
int[] prices = {1, 3, 2, 8, 4, 9};
int fee = 2;
Console.WriteLine("Maximum profit: " + sol.MaxProfit(prices, fee));
}
}The Python solution uses two variables, cash and hold, initialized appropriately to represent no stock and bought stock states respectively. On each day, the optimal choice between selling and holding, or buying and holding, is computed using the max function, ensuring maximum profit accounting for the transaction fee.
Time Complexity: O(N) since we pass through the list of prices once.
Space Complexity: O(1), as the extra variables used remain constant in 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.
class Solution:
def maxProfit(self, prices, fee):
max_profit, min_price = 0, prices[0]
for price in prices[1:]:
if price < min_price:
min_price = price
elif price > min_price + fee:
max_profit += price - min_price - fee
min_price = price - fee
return max_profit
if __name__ == "__main__":
sol = Solution()
prices = [1, 3, 2, 8, 4, 9]
fee = 2
print("Maximum profit:", sol.maxProfit(prices, fee))class Solution {
public int maxProfit(int[] prices, int fee) {
int maxProfit = 0, minPrice = prices[0];
for (int i = 1; i < prices.length; ++i) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] > minPrice + fee) {
maxProfit += prices[i] - minPrice - fee;
minPrice = prices[i] - fee;
}
}
return maxProfit;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] prices = {1, 3, 2, 8, 4, 9};
int fee = 2;
System.out.println("Maximum profit: " + sol.maxProfit(prices, fee));
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int maxProfit = 0;
int minPrice = prices[0];
for (int i = 1; i < prices.size(); ++i) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] > minPrice + fee) {
maxProfit += prices[i] - minPrice - fee;
minPrice = prices[i] - fee;
}
}
return maxProfit;
}
};
int main() {
vector<int> prices = {1, 3, 2, 8, 4, 9};
int fee = 2;
Solution sol;
int result = sol.maxProfit(prices, fee);
return 0;
}var maxProfit = function(prices, fee) {
let maxProfit = 0, minPrice = prices[0];
for (let i = 1; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] > minPrice + fee) {
maxProfit += prices[i] - minPrice - fee;
minPrice = prices[i] - fee;
}
}
return maxProfit;
};
console.log(maxProfit([1, 3, 2, 8, 4, 9], 2));#include <stdio.h>
int maxProfit(int* prices, int pricesSize, int fee) {
int maxProfit = 0;
int minPrice = prices[0];
for (int i = 1; i < pricesSize; ++i) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] > minPrice + fee) {
maxProfit += prices[i] - minPrice - fee;
minPrice = prices[i] - fee;
}
}
return maxProfit;
}
int main() {
int prices[] = {1, 3, 2, 8, 4, 9};
int fee = 2;
printf("Maximum profit: %d", maxProfit(prices, 6, fee));
return 0;
}using System;
public class Solution {
public int MaxProfit(int[] prices, int fee) {
int maxProfit = 0, minPrice = prices[0];
for (int i = 1; i < prices.Length; ++i) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] > minPrice + fee) {
maxProfit += prices[i] - minPrice - fee;
minPrice = prices[i] - fee;
}
}
return maxProfit;
}
public static void Main(string[] args) {
var sol = new Solution();
int[] prices = {1, 3, 2, 8, 4, 9};
int fee = 2;
Console.WriteLine("Maximum profit: " + sol.MaxProfit(prices, fee));
}
}The Python solution iterates over the prices list computing maximum possible profit by considering only instances when selling surpasses the transaction fee. It adjusts the min_price reactively based on transactions.
Time Complexity: O(N), since each price is processed without looping.
Space Complexity: O(1), minimal extra variable utilization.
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.
function maxProfit(prices: number[], fee: number): number {
const n = prices.length;
const f: number[][] = Array.from({ length: n }, () => [-1, -1]);
const dfs = (i: number, j: number): number => {
if (i >= n) {
return 0;
}
if (f[i][j] !== -1) {
return f[i][j];
}
let ans = dfs(i + 1, j);
if (j) {
ans = Math.max(ans, prices[i] + dfs(i + 1, 0) - fee);
} else {
ans = Math.max(ans, -prices[i] + dfs(i + 1, 1));
}
return (f[i][j] = ans);
};
return dfs(0, 0);
}func maxProfit(prices []int, fee int) int {
n := len(prices)
f := make([][2]int, n)
for i := range f {
f[i] = [2]int{-1, -1}
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i >= n {
return 0
}
if f[i][j] != -1 {
return f[i][j]
}
ans := dfs(i+1, j)
if j > 0 {
ans = max(ans, prices[i]+dfs(i+1, 0)-fee)
} else {
ans = max(ans, -prices[i]+dfs(i+1, 1))
}
f[i][j] = ans
return ans
}
return dfs(0, 0)
}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).
function maxProfit(prices: number[], fee: number): number {
const n = prices.length;
const f: number[][] = Array.from({ length: n }, () => [0, 0]);
f[0][1] = -prices[0];
for (let i = 1; i < n; ++i) {
f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i] - fee);
f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - prices[i]);
}
return f[n - 1][0];
}func maxProfit(prices []int, fee int) int {
n := len(prices)
f := make([][2]int, n)
f[0][1] = -prices[0]
for i := 1; i < n; i++ {
f[i][0] = max(f[i-1][0], f[i-1][1]+prices[i]-fee)
f[i][1] = max(f[i-1][1], f[i-1][0]-prices[i])
}
return f[n-1][0]
}Approach 5: Default Approach
function maxProfit(prices: number[], fee: number): number {
const n = prices.length;
let [f0, f1] = [0, -prices[0]];
for (const x of prices.slice(1)) {
[f0, f1] = [Math.max(f0, f1 + x - fee), Math.max(f1, f0 - x)];
}
return f0;
}func maxProfit(prices []int, fee int) int {
f0, f1 := 0, -prices[0]
for _, x := range prices[1:] {
f0, f1 = max(f0, f1+x-fee), max(f1, f0-x)
}
return f0
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(N) since we pass through the list of prices once. Space Complexity: O(1), as the extra variables used remain constant in size. |
| Greedy Approach | Time Complexity: O(N), since each price is processed without looping. Space Complexity: O(1), minimal extra variable utilization. |
| Memoization | – |
| Dynamic Programming | – |
| Default Approach | – |
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 |
Frequently asked questions
Is Best Time to Buy and Sell Stock with Transaction Fee easy or hard?
The problem is rated Medium because it requires recognizing the dynamic programming state transitions behind stock trading decisions. Once the hold/cash pattern is understood, the implementation becomes straightforward with a single linear pass.
Best Time to Buy and Sell Stock with Transaction Fee Python/Java solution
In both Python and Java, the solution iterates through the prices array while maintaining two variables: hold and cash. For each price, update hold using max(hold, cash - price) and update cash using max(cash, hold + price - fee). This implementation runs in O(n) time and constant space.
How to solve Best Time to Buy and Sell Stock with Transaction Fee in O(n)?
Maintain two variables while iterating through the array: hold for the best profit after buying and cash for the best profit after selling. Update them for each price using transitions: hold = max(hold, cash - price) and cash = max(cash, hold + price - fee). This single pass computes the maximum achievable profit.
What is the best approach for Best Time to Buy and Sell Stock with Transaction Fee?
The most reliable approach uses dynamic programming with two states: hold (profit when owning a stock) and cash (profit when not holding). Iterating once through the prices updates these states based on buy and sell decisions. This runs in O(n) time and O(1) space and generalizes well to other stock trading variants.
Is Best Time to Buy and Sell Stock with Transaction Fee asked at Google/Amazon/Meta?
Stock trading dynamic programming problems frequently appear in interviews at large tech companies such as Amazon, Google, Meta, and Microsoft. Variations of the stock buy and sell series are commonly used to test dynamic programming and greedy reasoning.
What data structure is used in Best Time to Buy and Sell Stock with Transaction Fee?
The solution primarily uses variables to track DP states while iterating through an array of prices. No complex data structures are required; the algorithm relies on dynamic programming state transitions or a greedy price-tracking strategy.
What is the time complexity of Best Time to Buy and Sell Stock with Transaction Fee?
The optimal solution runs in O(n) time because you scan the prices array once while updating profit states. Space complexity is O(1) since only two variables (hold and cash) are maintained instead of a full DP table.