Scale Engineer

Best Time to Buy and Sell Stock with Transaction Fee

Med
#0668Time: 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.1 company
Patterns
Dynamic ProgrammingGreedy
Data structures
Array
Companies
Citadel

Prompt

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 * 104
  • 1 <= prices[i] < 5 * 104
  • 0 <= 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 day index onwards.
  • The holding parameter indicates if we currently possess a stock.
  • Base Case: If index goes beyond the array bounds, return 0 as no more profit can be made.
  • Recursive Step:
    • If holding is 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.
    • If holding is 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.
  • 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.

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem