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 * 104The key challenge in #714 Best Time to Buy and Sell Stock with Transaction Fee is deciding when to buy and sell while accounting for a fixed transaction fee applied to each sale. A common strategy is to model the problem using dynamic programming with two states: holding a stock and not holding a stock. At each day, you decide whether to buy, sell, or do nothing based on the maximum profit achievable so far.
You can track two variables: one representing the profit if you currently hold a stock, and another representing the profit if you are in cash (not holding any stock). When selling, subtract the transaction fee to reflect the true profit. This formulation ensures that every decision considers the optimal previous state.
The approach can also be viewed as a greedy optimization of the DP transitions, allowing constant space usage while iterating through prices once. The algorithm processes each price in linear time, making it efficient for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming / Greedy State Optimization | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Consider the first K stock prices. At the end, the only legal states are that you don't own a share of stock, or that you do. Calculate the most profit you could have under each of these two cases.
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.
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.
1using System;
2
3public class Solution {
4 public int MaxProfit(int[] prices, int fee) {
5 int cash = 0, hold = -prices[0];
6 for (int i = 1; i < prices.Length; ++i) {
7 cash = Math.Max(cash, hold + prices[i] - fee);
8 hold = Math.Max(hold, cash - prices[i]);
9 }
10 return cash;
11 }
12 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));
}
}In C#, the solution mirrors those in other languages with similar principles. We use cash and hold to track potential profit scenarios. Within the loop, leverage Math.Max to ensure that the most profitable decision is made each day, taking into account transaction fees.
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.
Time Complexity: O(N), since it processes each price once.
Space Complexity: O(1), using a constant set of additional variables.
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));
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, stock trading problems with variations like transaction fees or cooldown periods are common in technical interviews at large tech companies. They test a candidate's understanding of dynamic programming and state transitions.
The optimal approach uses dynamic programming with two states: holding a stock and not holding a stock. By updating these states for each price and subtracting the transaction fee when selling, you can compute the maximum profit in a single pass.
Yes. The problem can be optimized from a dynamic programming formulation into a greedy-style solution by maintaining two variables representing the best profit while holding or not holding a stock. This keeps the time complexity linear and space constant.
The problem mainly relies on simple variables rather than complex data structures. Since only the previous state matters, two variables are enough to track the optimal profit transitions across the price array.
The C# solution adopts a logical pattern consistent with other greedy implementations, determining to sell stock when it yields net gain surpassing the fee, and adjusting trackers thereafter.