Best Time to Buy and Sell Stock with Transaction Fee
MedPrompt
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
Approaches
4 approaches with complexity analysis and trade-offs.
This approach directly translates the problem into a recursive solution. For each day, we explore every possible action: if we hold a stock, we can either sell it or continue holding it; if we don't hold a stock, we can either buy one or rest. This generates a decision tree where every path represents a sequence of transactions, and we aim to find the path with the maximum profit.
Algorithm
- Define a recursive function
calculate(index, holding)that returns the maximum profit from dayindexonwards. - The
holdingparameter indicates if we currently possess a stock. - Base Case: If
indexgoes beyond the array bounds, return 0 as no more profit can be made. - Recursive Step:
- If
holdingis true (we have a stock):- Option 1 (Sell):
profit = prices[index] - fee + calculate(index + 1, false). - Option 2 (Hold):
profit = calculate(index + 1, true). - Return the maximum of the two options.
- Option 1 (Sell):
- If
holdingis false (we don't have a stock):- Option 1 (Buy):
profit = -prices[index] + calculate(index + 1, true). - Option 2 (Rest):
profit = calculate(index + 1, false). - Return the maximum of the two options.
- Option 1 (Buy):
- If
- The initial call is
calculate(0, false).
Walkthrough
The brute-force method uses a recursive function to explore all possible sequences of buying and selling stocks. The function takes the current day's index and a boolean indicating whether a stock is currently held. From any given state, it recursively calls itself for the next day for all possible actions (buy/rest or sell/hold) and returns the maximum profit found among these choices. This exhaustive search guarantees finding the optimal solution but at a very high computational cost.
class Solution { public int maxProfit(int[] prices, int fee) { return calculate(prices, fee, 0, false); } private int calculate(int[] prices, int fee, int index, boolean holding) { if (index == prices.length) { return 0; } // Option to do nothing and move to the next day int doNothing = calculate(prices, fee, index + 1, holding); int doSomething; if (holding) { // Option to sell the stock doSomething = prices[index] - fee + calculate(prices, fee, index + 1, false); } else { // Option to buy the stock doSomething = -prices[index] + calculate(prices, fee, index + 1, true); } return Math.max(doNothing, doSomething); }}Complexity
Time
O(2^N), where N is the length of the `prices` array. For each day, the function branches into two possibilities, leading to an exponential number of calls.
Space
O(N), where N is the number of days. This space is used by the recursion stack.
Trade-offs
Pros
Simple to conceptualize and implement.
Directly models the decision-making process at each step.
Cons
Extremely inefficient due to re-computation of the same subproblems.
Will result in a 'Time Limit Exceeded' error on any reasonably sized input.
The brute-force approach suffers from re-calculating the same subproblems multiple times. We can optimize this by using memoization, a top-down dynamic programming technique. We store the results of each unique state (defined by the current day and whether we hold a stock) in a cache or table. When we encounter a state we've seen before, we simply retrieve the stored result instead of re-computing it.
Algorithm
- Use the same recursive structure as the brute-force approach.
- Create a 2D memoization table,
memo[n][2], wherenis the number of days.memo[i][0]will store the max profit from dayiif not holding a stock, andmemo[i][1]if holding one. - Initialize the table with a sentinel value (e.g.,
nullor -1) to indicate that a state has not been computed. - In the recursive function, before any computation, check if the result for the current state
(index, holding)is already in the memoization table. If so, return it directly. - If not, compute the result as in the brute-force approach, store it in the table, and then return it.
Walkthrough
We enhance the recursive solution by adding a memoization table, typically a 2D array memo[prices.length][2]. The state is defined by (index, holding), where holding is 0 for not holding a stock and 1 for holding one. Before the recursive logic, we check memo[index][holding]. If it contains a valid, previously computed result, we return it. Otherwise, we perform the calculation, store the result in memo[index][holding], and then return it. This ensures that each of the N * 2 states is computed only once.
class Solution { Integer[][] memo; int[] prices; int fee; public int maxProfit(int[] prices, int fee) { this.prices = prices; this.fee = fee; this.memo = new Integer[prices.length][2]; return calculate(0, 0); // 0: not holding, 1: holding } private int calculate(int index, int holding) { if (index == prices.length) { return 0; } if (memo[index][holding] != null) { return memo[index][holding]; } // Case 1: Do nothing today (rest or hold) int doNothing = calculate(index + 1, holding); int doSomething; if (holding == 1) { // Currently holding a stock // Option 2: Sell the stock doSomething = prices[index] - fee + calculate(index + 1, 0); } else { // Currently not holding a stock // Option 2: Buy the stock doSomething = -prices[index] + calculate(index + 1, 1); } memo[index][holding] = Math.max(doNothing, doSomething); return memo[index][holding]; }}Complexity
Time
O(N), where N is the number of days. Each of the `N * 2` states is computed exactly once.
Space
O(N) for both the memoization table (`N x 2`) and the recursion stack depth.
Trade-offs
Pros
Drastically improves time complexity from exponential to linear.
Guaranteed to be efficient enough for the given constraints.
Maintains the intuitive recursive structure.
Cons
Requires O(N) extra space for the memoization table.
May have slightly more overhead than the iterative tabulation approach due to recursive function calls.
This approach, also known as bottom-up dynamic programming, solves the problem iteratively. We build a table to store the maximum profit at each day for two possible states: holding a stock or not holding a stock. We fill the table starting from day 0 and use the results of the previous day to compute the results for the current day.
Algorithm
- Create a 2D DP table
dp[n][2], wheredp[i][0]is the max profit on dayiending with no stock, anddp[i][1]is the max profit on dayiending with a stock. - Base Case (Day 0):
dp[0][0] = 0(start with no stock, no profit).dp[0][1] = -prices[0](buy on day 0).
- Iteration: Loop from
i = 1ton-1.dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee).dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]).
- Result: The final answer is
dp[n-1][0], as it's always optimal to not be holding a stock on the last day.
Walkthrough
We define our DP states as follows:
dp[i][0]: The maximum profit achievable at the end of dayi, given that we do not hold any stock.dp[i][1]: The maximum profit achievable at the end of dayi, given that we hold one share of the stock.
We can establish the following recurrence relations:
- To have no stock on day
i, we could have either rested from dayi-1(if we had no stock) or sold the stock we held on dayi-1. Thus,dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee). - To have a stock on day
i, we could have either held onto the stock from dayi-1or bought a stock today (if we had no stock on dayi-1). Thus,dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]).
The base cases for day 0 are dp[0][0] = 0 and dp[0][1] = -prices[0]. We iterate up to the last day and return dp[n-1][0].
class Solution { public int maxProfit(int[] prices, int fee) { int n = prices.length; if (n == 0) { return 0; } int[][] dp = new int[n][2]; // Base case for day 0 dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < n; i++) { // Max profit with no stock today dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i] - fee); // Max profit with a stock today dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); } return dp[n - 1][0]; }}Complexity
Time
O(N), as we iterate through the prices array once to fill the DP table.
Space
O(N) to store the `dp` table of size `N x 2`.
Trade-offs
Pros
Efficient O(N) time complexity.
Avoids recursion overhead, which can make it slightly faster in practice than memoization.
The state transitions are very clear and easy to follow.
Cons
Uses O(N) space, which is not optimal for this problem.
This is the most optimized approach. By observing the recurrence relations in the tabular DP approach, we can see that the calculation for day i only depends on the values from day i-1. This means we don't need to store the entire DP table. We only need to keep track of the maximum profit for the two states (holding a stock and not holding one) from the previous day. This reduces the space complexity to a constant.
Algorithm
- Initialize two variables:
cash = 0(max profit ending with no stock) andhold = -prices[0](max profit ending with a stock). - Iterate through the prices from the second day (
i = 1ton-1). - In each iteration, update the
cashandholdvariables based on the previous day's values:- Store the previous
cashvalue in a temporary variable:prev_cash = cash. - Update
cash:cash = max(cash, hold + prices[i] - fee). - Update
hold:hold = max(hold, prev_cash - prices[i]).
- Store the previous
- After the loop, return
cash.
Walkthrough
We can optimize the space complexity of the tabular DP approach from O(N) to O(1). We only need two variables to track the maximum profit at the end of the previous day: cash for the state of not holding a stock, and hold for the state of holding a stock.
We iterate through the prices, and for each day, we calculate the new cash and hold values. The new cash value is the maximum of either not doing anything (keeping the old cash value) or selling the stock (which depends on the old hold value). The new hold value is the maximum of either holding onto the stock (keeping the old hold value) or buying a stock (which depends on the old cash value). It's important to use the cash value from the previous day when calculating the new hold value, so we use a temporary variable.
class Solution { public int maxProfit(int[] prices, int fee) { int n = prices.length; if (n == 0) { return 0; } // `cash`: max profit if we end the day with no stock int cash = 0; // `hold`: max profit if we end the day holding a stock int hold = -prices[0]; for (int i = 1; i < n; i++) { int prev_cash = cash; // New cash state is max of (rest from prev cash) or (sell from prev hold) cash = Math.max(cash, hold + prices[i] - fee); // New hold state is max of (rest from prev hold) or (buy from prev cash) hold = Math.max(hold, prev_cash - prices[i]); } return cash; }}Complexity
Time
O(N), as it involves a single pass through the input array.
Space
O(1), as we only use a few constant-space variables to store the state.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1).
Very efficient and concise implementation.
Cons
The logic can be slightly less intuitive to grasp initially compared to the version with an explicit DP table.
Solutions
Solution
class Solution {public int maxProfit(int[] prices, int fee) { int f0 = 0, f1 = -prices[0]; for (int i = 1; i < prices.length; ++i) { int g0 = Math.max(f0, f1 + prices[i] - fee); f1 = Math.max(f1, f0 - prices[i]); f0 = g0; } return f0; }}class Solution {public: int maxProfit(vector<int> &prices, int fee) { int n = prices.size(); int f[n][2]; memset(f, 0, sizeof(f)); f[0][1] = -prices[0]; for (int 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]; }};class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: f1, f2 = - prices[0], 0 for price in prices[1:]: f1 = max(f1, f2 - price) f2 = max(f2, f1 + price - fee) return f2 # class Solution : def maxProfit ( self , prices : List [ int ], fee : int ) -> int : f0 , f1 = 0 , - prices [ 0 ] for x in prices [ 1 :]: f0 , f1 = max ( f0 , f1 + x - fee ), max ( f1 , f0 - x ) return f0 ############ class Solution : def maxProfit ( self , prices , fee ): """ :type prices: List[int] :type fee: int :rtype: int """ cash = 0 hold = - prices [ 0 ] for i in range ( 1 , len ( prices )): cash = max ( cash , hold + prices [ i ] - fee ) hold = max ( hold , cash - prices [ i ]) return cashVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.