Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Best Time to Buy and Sell Stock with Transaction Fee

MEDIUMProblemSolveExternal Links

Description

You are given an array prices where prices[i] represents the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Your goal is to find the maximum profit you can achieve. You may complete as many transactions as you like (buy one share and sell one share of the stock multiple times), but you must pay the transaction fee for each transaction (each buy-sell pair).

Rules:

  • You cannot hold more than one share at a time — you must sell the stock before buying again.
  • The transaction fee is charged once per complete buy-sell transaction.
  • You want to maximize total profit after accounting for all fees.

Examples

Example 1

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2

Output: 8

Explanation: The maximum profit is achieved by two transactions:

  • Transaction 1: Buy at price 1 (day 0), sell at price 8 (day 3). Profit = (8 - 1) - 2 = 5.
  • Transaction 2: Buy at price 4 (day 4), sell at price 9 (day 5). Profit = (9 - 4) - 2 = 3.
  • Total profit = 5 + 3 = 8.

Notice that buying at 1 and selling at 3 (profit = 3 - 1 - 2 = 0) would yield zero profit, so it is better to hold and sell later at 8.

Example 2

Input: prices = [1, 3, 7, 5, 10, 3], fee = 3

Output: 6

Explanation: The maximum profit is achieved by one transaction:

  • Transaction 1: Buy at price 1 (day 0), sell at price 10 (day 4). Profit = (10 - 1) - 3 = 6.
  • Splitting into two trades (e.g., buy at 1, sell at 7, buy at 5, sell at 10) would give (7-1-3) + (10-5-3) = 3 + 2 = 5, which is worse because we pay the fee twice.
  • Total profit = 6.

Example 3

Input: prices = [2, 1, 4, 4, 2, 3, 2, 5, 1, 2], fee = 1

Output: 6

Explanation: Multiple small transactions can be combined:

  • Buy at 1 (day 1), sell at 4 (day 2). Profit = (4-1)-1 = 2.
  • Buy at 2 (day 4), sell at 5 (day 7). Profit = (5-2)-1 = 2.
  • Buy at 1 (day 8), sell at 2 (day 9). Profit = (2-1)-1 = 0. This transaction is break-even so it does not help.

Actually, optimal is buy at 1, sell at 4 (profit 2), buy at 2, sell at 5 (profit 2), buy at 1, sell at 2 (profit 0) — total 4. Even better: buy at 1 (day 1), sell at 4 (day 2), buy at 2 (day 4), sell at 3 (day 5) = 0, buy at 2 (day 6), sell at 5 (day 7) = 2. Total = 2+0+2 = 4. The optimal strategy gives profit = 6: buy at 1, sell at 4 (profit 2), then buy at 2, sell at 5 (profit 2), then buy at 1, sell at 2... Actually the DP yields 6. Total profit = 6.

Constraints

  • 1 ≤ prices.length ≤ 5 × 10^4
  • 1 ≤ prices[i] < 5 × 10^4
  • 0 ≤ fee < 5 × 10^4

Editorial

Brute Force

Intuition

The most straightforward way to think about this problem is to consider every possible sequence of buy-sell decisions. On each day, you have a choice that depends on your current state:

  • If you do NOT hold a stock: You can either buy today (paying the current price) or skip (do nothing).
  • If you DO hold a stock: You can either sell today (receiving the current price minus the fee) or skip (keep holding).

We can model this as a recursive function that tries both options at every day and returns the maximum profit achievable from that day onward.

Think of it like planning a road trip: at every intersection (day), you have two choices. You try both routes, see which leads to the highest reward at the end, and pick the better one. The problem is that the number of intersections is huge, so exploring every route becomes incredibly slow.

Step-by-Step Explanation

Let's trace with prices = [1, 3, 2, 8, 4, 9], fee = 2:

Step 1: Start at day 0, not holding stock. Profit so far = 0.

  • Option A: Buy at price 1 → holding = true, move to day 1
  • Option B: Skip → holding = false, move to day 1

Step 2: Following Option A (bought at day 0, holding). At day 1, price = 3.

  • Option A1: Sell at price 3, pay fee → profit += 3 - 2 = 1, holding = false, move to day 2
  • Option A2: Skip (keep holding) → move to day 2

Step 3: Following A2 (still holding from day 0). At day 2, price = 2.

  • Option: Skip or sell at 2 (profit = 2 - 2 = 0). Skip is better. Move to day 3.

Step 4: At day 3, price = 8, still holding.

  • Option: Sell at 8, pay fee → profit += 8 - 2 = 6. Not holding, move to day 4.

Step 5: At day 4, price = 4, not holding.

  • Option: Buy at 4 → holding, move to day 5.

Step 6: At day 5, price = 9, holding.

  • Option: Sell at 9, pay fee → profit += 9 - 2 = 7.

Total profit for this path: buy at 1, sell at 8 (profit 8-1-2=5), buy at 4, sell at 9 (profit 9-4-2=3) = 8.

But the brute force tries ALL paths — including suboptimal ones like selling at day 1 — before determining the maximum.

Stock Trading — Recursive Decision Tree — Watch how the recursive approach branches at every day: buy or skip (if not holding), sell or skip (if holding). Many branches lead to suboptimal results, and overlapping subproblems are computed repeatedly.

Algorithm

  1. Define a recursive function solve(day, holding) that returns the maximum profit achievable from day onward, given whether we currently hold a stock.
  2. Base case: If day == n (past the last day), return 0 (no more trades possible). If holding, we cannot sell past the end, so holding stock at the end is worth 0.
  3. If not holding: Try buy (recurse with day+1, holding=true, subtract prices[day]) or skip (recurse with day+1, holding=false). Return the maximum.
  4. If holding: Try sell (recurse with day+1, holding=false, add prices[day] - fee) or skip (recurse with day+1, holding=true). Return the maximum.
  5. Call solve(0, false) to get the answer.

Code

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        return solve(prices, fee, 0, false);
    }
    
    int solve(vector<int>& prices, int fee, int day, bool holding) {
        if (day == prices.size()) return 0;
        
        if (holding) {
            // Option 1: sell today
            int sellProfit = prices[day] - fee + solve(prices, fee, day + 1, false);
            // Option 2: skip (keep holding)
            int skipProfit = solve(prices, fee, day + 1, true);
            return max(sellProfit, skipProfit);
        } else {
            // Option 1: buy today
            int buyProfit = -prices[day] + solve(prices, fee, day + 1, true);
            // Option 2: skip
            int skipProfit = solve(prices, fee, day + 1, false);
            return max(buyProfit, skipProfit);
        }
    }
};
class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        def solve(day: int, holding: bool) -> int:
            if day == len(prices):
                return 0
            
            if holding:
                # Option 1: sell today
                sell_profit = prices[day] - fee + solve(day + 1, False)
                # Option 2: skip
                skip_profit = solve(day + 1, True)
                return max(sell_profit, skip_profit)
            else:
                # Option 1: buy today
                buy_profit = -prices[day] + solve(day + 1, True)
                # Option 2: skip
                skip_profit = solve(day + 1, False)
                return max(buy_profit, skip_profit)
        
        return solve(0, False)
class Solution {
    public int maxProfit(int[] prices, int fee) {
        return solve(prices, fee, 0, false);
    }
    
    private int solve(int[] prices, int fee, int day, boolean holding) {
        if (day == prices.length) return 0;
        
        if (holding) {
            int sellProfit = prices[day] - fee + solve(prices, fee, day + 1, false);
            int skipProfit = solve(prices, fee, day + 1, true);
            return Math.max(sellProfit, skipProfit);
        } else {
            int buyProfit = -prices[day] + solve(prices, fee, day + 1, true);
            int skipProfit = solve(prices, fee, day + 1, false);
            return Math.max(buyProfit, skipProfit);
        }
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each of the n days, we make two recursive calls (buy/sell and skip). This creates a binary recursion tree of depth n, resulting in up to 2^n calls. For n = 50,000, this is astronomically large and will never finish in time.

Space Complexity: O(n)

The recursion depth is at most n (one call per day), so the call stack uses O(n) space.

Why This Approach Is Not Efficient

The brute force recursion has O(2^n) time complexity. With n up to 50,000, this is completely infeasible.

The root cause is overlapping subproblems. The state of our recursion is fully determined by just two variables: day (which day we're on) and holding (whether we hold a stock or not). There are only n × 2 = 2n unique states! But the naive recursion re-computes the same states exponentially many times through different decision paths.

For example, solve(day=3, holding=true) might be reached by:

  • Buy day 0 → skip day 1 → skip day 2 → day 3 holding
  • Skip day 0 → buy day 1 → skip day 2 → day 3 holding
  • Skip day 0 → skip day 1 → buy day 2 → day 3 holding

All three paths lead to the same state, but we compute it three times.

Key insight: by storing results in a dp[day][holding] table, we compute each state exactly once, reducing time from O(2^n) to O(n).

Better Approach - Dynamic Programming (Tabulation)

Intuition

Instead of recursing from day 0 forward, we can fill a DP table from the last day backward (or equivalently, from day 0 forward).

Define two arrays:

  • dp[i][0] = maximum profit achievable from day i onward if we are NOT holding a stock at the start of day i.
  • dp[i][1] = maximum profit achievable from day i onward if we ARE holding a stock at the start of day i.

Transitions (forward-style, processing day by day):

  • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)
    • Either we were not holding yesterday and do nothing, OR we were holding yesterday and sell today (gaining price minus fee).
  • dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
    • Either we were holding yesterday and do nothing, OR we were not holding yesterday and buy today (spending price).

Base case (day 0):

  • dp[0][0] = 0 — not holding, no profit yet.
  • dp[0][1] = -prices[0] — holding after buying on day 0, so we spent prices[0].

The answer is dp[n-1][0] — maximum profit at the end when not holding any stock.

Think of it as maintaining two parallel "bank accounts": one for when you're empty-handed, one for when you're holding stock. Each day, both accounts update based on the best possible action.

Step-by-Step Explanation

Let's trace with prices = [1, 3, 2, 8, 4, 9], fee = 2:

Step 1: Initialize day 0.

  • dp[0][0] = 0 (not holding, no profit)
  • dp[0][1] = -1 (holding after buying at price 1)

Step 2: Day 1, price = 3.

  • dp[1][0] = max(dp[0][0], dp[0][1] + 3 - 2) = max(0, -1 + 1) = max(0, 0) = 0
  • dp[1][1] = max(dp[0][1], dp[0][0] - 3) = max(-1, -3) = -1

Step 3: Day 2, price = 2.

  • dp[2][0] = max(dp[1][0], dp[1][1] + 2 - 2) = max(0, -1 + 0) = max(0, -1) = 0
  • dp[2][1] = max(dp[1][1], dp[1][0] - 2) = max(-1, -2) = -1

Step 4: Day 3, price = 8.

  • dp[3][0] = max(dp[2][0], dp[2][1] + 8 - 2) = max(0, -1 + 6) = max(0, 5) = 5
  • dp[3][1] = max(dp[2][1], dp[2][0] - 8) = max(-1, -8) = -1

Step 5: Day 4, price = 4.

  • dp[4][0] = max(dp[3][0], dp[3][1] + 4 - 2) = max(5, -1 + 2) = max(5, 1) = 5
  • dp[4][1] = max(dp[3][1], dp[3][0] - 4) = max(-1, 5 - 4) = max(-1, 1) = 1

Step 6: Day 5, price = 9.

  • dp[5][0] = max(dp[4][0], dp[4][1] + 9 - 2) = max(5, 1 + 7) = max(5, 8) = 8
  • dp[5][1] = max(dp[4][1], dp[4][0] - 9) = max(1, -4) = 1

Result: dp[5][0] = 8.

Stock with Fee — DP Table Forward Pass — Watch how we maintain two running values — cash (not holding) and hold (holding stock) — as we process each day's price. The values propagate forward, always choosing the best decision at each step.

Algorithm

  1. Create two arrays cash and hold of size n.
  2. Initialize: cash[0] = 0, hold[0] = -prices[0].
  3. For each day i from 1 to n-1:
    • cash[i] = max(cash[i-1], hold[i-1] + prices[i] - fee)
    • hold[i] = max(hold[i-1], cash[i-1] - prices[i])
  4. Return cash[n-1].

Code

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<int> cash(n), hold(n);
        cash[0] = 0;
        hold[0] = -prices[0];
        
        for (int i = 1; i < n; i++) {
            cash[i] = max(cash[i - 1], hold[i - 1] + prices[i] - fee);
            hold[i] = max(hold[i - 1], cash[i - 1] - prices[i]);
        }
        
        return cash[n - 1];
    }
};
class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        n = len(prices)
        cash = [0] * n
        hold = [0] * n
        cash[0] = 0
        hold[0] = -prices[0]
        
        for i in range(1, n):
            cash[i] = max(cash[i - 1], hold[i - 1] + prices[i] - fee)
            hold[i] = max(hold[i - 1], cash[i - 1] - prices[i])
        
        return cash[n - 1]
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[] cash = new int[n];
        int[] hold = new int[n];
        cash[0] = 0;
        hold[0] = -prices[0];
        
        for (int i = 1; i < n; i++) {
            cash[i] = Math.max(cash[i - 1], hold[i - 1] + prices[i] - fee);
            hold[i] = Math.max(hold[i - 1], cash[i - 1] - prices[i]);
        }
        
        return cash[n - 1];
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the prices array exactly once. At each step, we perform a constant number of comparisons and assignments. Total: n iterations × O(1) per iteration = O(n).

Space Complexity: O(n)

We maintain two arrays (cash and hold), each of size n, to store the DP values for every day. This requires O(n) additional memory.

Why This Approach Is Not Efficient

The DP tabulation approach achieves optimal O(n) time complexity, which cannot be improved since we must examine each price at least once. However, it uses O(n) space for the two arrays.

When we look at the recurrence, cash[i] depends only on cash[i-1] and hold[i-1], and hold[i] depends only on hold[i-1] and cash[i-1]. This means we never need to look back more than one day — the rest of the arrays are dead data.

We can replace the two arrays with just two scalar variables, reducing space from O(n) to O(1). For n up to 50,000, the O(n) space is acceptable, but O(1) space is cleaner and more efficient in practice, especially for very large inputs or memory-constrained environments.

Optimal Approach - Space-Optimized DP (Greedy-Like)

Intuition

The core idea remains the same as the tabulation approach, but we recognize that we only need two numbers from the previous day: cash (best profit when not holding) and hold (best profit when holding).

At each day, we update:

  • cash = max(cash, hold + price - fee) — either stay idle, or sell today
  • hold = max(hold, cash - price) — either keep holding, or buy today

This is almost like a greedy algorithm: at every moment, we keep track of the best possible position for each state, always choosing the action that maximizes our advantage.

Think of cash as your wallet when you are empty-handed, and hold as your wallet adjusted for a stock you are carrying. Each day, you peek at the price and decide: is it worth transacting, or should I wait? The beauty is that by the end, cash naturally contains the maximum profit.

Important detail: When updating cash and hold on the same day, the order matters. We compute the new cash first using the old hold, and then compute the new hold using the new cash. This works correctly because if we sell and buy on the same day, it is equivalent to not transacting at all (the sell and buy cancel out).

Step-by-Step Explanation

Let's trace with prices = [1, 3, 2, 8, 4, 9], fee = 2:

Step 1: Initialize: cash = 0, hold = -1 (bought at price 1).

Step 2: Day 1, price = 3.

  • new_cash = max(0, -1 + 3 - 2) = max(0, 0) = 0
  • new_hold = max(-1, 0 - 3) = max(-1, -3) = -1
  • cash = 0, hold = -1. No change — selling at 3 with fee 2 gives zero gain.

Step 3: Day 2, price = 2.

  • new_cash = max(0, -1 + 2 - 2) = max(0, -1) = 0
  • new_hold = max(-1, 0 - 2) = max(-1, -2) = -1
  • cash = 0, hold = -1. Still no improvement.

Step 4: Day 3, price = 8.

  • new_cash = max(0, -1 + 8 - 2) = max(0, 5) = 5
  • new_hold = max(-1, 5 - 8) = max(-1, -3) = -1
  • cash = 5, hold = -1. Big jump! Selling at 8 locks in profit of 5.

Step 5: Day 4, price = 4.

  • new_cash = max(5, -1 + 4 - 2) = max(5, 1) = 5
  • new_hold = max(-1, 5 - 4) = max(-1, 1) = 1
  • cash = 5, hold = 1. We buy at 4 using our 5 profit → hold = 1.

Step 6: Day 5, price = 9.

  • new_cash = max(5, 1 + 9 - 2) = max(5, 8) = 8
  • new_hold = max(1, 5 - 9) = max(1, -4) = 1
  • cash = 8, hold = 1. Selling at 9 gives total profit of 8!

Result: cash = 8.

Space-Optimized DP — Two Variables Walk Through Prices — Watch how just two variables (cash and hold) evolve as we process each day's price. At each step, we decide whether it is worth buying, selling, or waiting.

Algorithm

  1. Initialize cash = 0 (max profit when not holding stock) and hold = -prices[0] (max profit when holding stock, having bought on day 0).
  2. For each day i from 1 to n-1:
    • cash = max(cash, hold + prices[i] - fee) — either stay idle or sell
    • hold = max(hold, cash - prices[i]) — either keep holding or buy
  3. Return cash.

Code

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        int cash = 0;           // max profit when not holding
        int hold = -prices[0];  // max profit when holding
        
        for (int i = 1; i < n; i++) {
            cash = max(cash, hold + prices[i] - fee);
            hold = max(hold, cash - prices[i]);
        }
        
        return cash;
    }
};
class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        cash = 0              # max profit when not holding
        hold = -prices[0]     # max profit when holding
        
        for i in range(1, len(prices)):
            cash = max(cash, hold + prices[i] - fee)
            hold = max(hold, cash - prices[i])
        
        return cash
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int cash = 0;             // max profit when not holding
        int hold = -prices[0];    // max profit when holding
        
        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;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make a single pass through the prices array. At each step, we perform two max operations and a few additions — all O(1). Total: n iterations × O(1) = O(n). For n = 50,000, this is 50,000 operations — extremely fast.

Space Complexity: O(1)

We use only two integer variables (cash and hold) regardless of the input size. No arrays, no hash maps, no recursion stack. This is the minimum possible space — we cannot solve this problem without at least reading the input and maintaining some state.