AlgoMaster Logo

Best Time to Buy and Sell Stock with Transaction Fee

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

This is a variation of the classic "buy and sell stock" problem: you can trade as many times as you want, but every completed transaction (a buy followed by a sell) costs a fixed fee. Without the fee, you would take every upward price movement. With the fee, a price rise only helps if it exceeds the fee, so small gains can cost more than they earn.

On any given day you are in one of two states, holding a stock or not holding one, and the best achievable profit depends on that state. Tracking the best profit for both states from one day to the next is the core of every approach below.

Key Constraints:

  • 1 <= prices.length <= 5 * 10^4: With n up to 50,000, an O(n) or O(n log n) algorithm is required. O(n^2) is about 2.5 billion operations at this size.
  • 1 <= prices[i] < 5 * 10^4: Total profit is bounded by the sum of positive day-to-day price changes, at most about 1.25 * 10^9, so it fits in a 32-bit signed integer.
  • 0 <= fee < 5 * 10^4: A fee of zero reduces this to the unlimited transactions problem (LeetCode #122), where every upward movement is worth taking.

Approach 1: Dynamic Programming with Arrays

Intuition

Each of the two daily states allows different moves. If you're not holding a stock, you can either do nothing (stay without stock) or buy a stock (transition to holding). If you're holding a stock, you can either do nothing (keep holding) or sell the stock and pay the fee (transition to not holding).

This maps directly onto a DP formulation. Define two arrays: cash[i] for the maximum profit on day i without holding stock, and hold[i] for the maximum profit on day i while holding stock. The recurrences are:

  • cash[i] = max(cash[i-1], hold[i-1] + prices[i] - fee) (did nothing, or sold today)
  • hold[i] = max(hold[i-1], cash[i-1] - prices[i]) (did nothing, or bought today)

On day 0, cash[0] = 0 and hold[0] = -prices[0]. The answer is cash[n-1]: ending while still holding a stock means money was spent on a purchase that was never recouped, so the not-holding state is always at least as good.

Algorithm

  1. Create two arrays cash and hold of length n.
  2. Initialize cash[0] = 0 and hold[0] = -prices[0].
  3. For each day from 1 to n-1, compute cash[i] and hold[i] using the recurrences above.
  4. Return cash[n-1].

Visualization and Code

Loading animation...

The time is already optimal, but we're using O(n) space to store the full history of both states. Since each day only depends on the previous day, we can collapse the arrays into two variables.

Approach 2: Space-Optimized DP

Intuition

Each day's values depend only on the previous day's values, so the full arrays are unnecessary. Replace cash[i] and hold[i] with two variables cash and hold, updated day by day.

One detail needs care: the update for hold should read the previous day's cash, so the code saves it in a temporary variable before overwriting it. In this particular problem the temporary is a safeguard rather than a necessity. Using the freshly updated cash would model selling and buying back on the same day, which pays a fee for nothing and never wins the max. Keeping the temporary makes the code match the recurrence exactly.

Algorithm

  1. Initialize cash = 0 and hold = -prices[0].
  2. For each day from 1 to n-1:
    • Save the current cash in a temporary variable.
    • Update cash = max(cash, hold + prices[i] - fee).
    • Update hold = max(hold, prevCash - prices[i]).
  3. Return cash.

Visualization and Code

Loading animation...

O(n) time and O(1) space cannot be improved, but a greedy method reaches the same bounds through different reasoning: track the effective cost of the current position and sell whenever the price covers that cost plus the fee.

Approach 3: Greedy

Intuition

Track the effective cost of your current position in a single variable buy. When the price drops below buy, the cheaper price becomes the new cost basis. When the price rises above buy + fee, sell and add prices[i] - buy - fee to the profit.

The subtle step is what happens after a sell: instead of treating the position as closed, set buy = prices[i] - fee. This makes the sell reversible. If a later price p is higher, the extra profit recorded then is p - (prices[i] - fee) - fee = p - prices[i], which is exactly the difference between selling at p and selling at prices[i]. The two sells together pay only one fee, the same as skipping the early sell and selling once at p. So selling as soon as prices[i] > buy + fee is safe: the locked-in profit is never lost, and any later, higher sell still earns its full increment on top.

Algorithm

  1. Initialize buy = prices[0] (the effective cost of our current position).
  2. Initialize profit = 0.
  3. For each day from 1 to n-1:
    • If prices[i] < buy: this is a cheaper buy opportunity, so update buy = prices[i].
    • If prices[i] > buy + fee: this sale is profitable, so add prices[i] - buy - fee to profit, and set buy = prices[i] - fee (the discounted cost basis, so a later higher sell pays no second fee).
  4. Return profit.

Visualization and Code

Loading animation...