714. Best Time to Buy and Sell Stock with Transaction Fee

LeetCode Problem Link (opens new window)

Given an integer array prices, where prices[i] is the price of a given stock on the i-th day, and an integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You cannot engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Return the maximum profit you can achieve.

Note: A transaction is defined as buying and holding the stock and then selling it, during which the transaction fee is applied once.

Example 1:

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

Explanation: The maximum profit can be achieved by:

• Buy on day 0: prices[0] = 1
• Sell on day 3: prices[3] = 8
• Buy on day 4: prices[4] = 4
• Sell on day 5: prices[5] = 9
• Total profit: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Constraints:

• 0 < prices.length <= 50000
• 0 < prices[i] < 50000
• 0 <= fee < 50000

Approach

The optimal way to solve this problem is using dynamic programming, which will be further discussed in future dynamic programming lessons.

Compared to 0122.Best Time to Buy and Sell Stock II (opens new window), this problem introduces a transaction fee.

Greedy Algorithm

In 0122.Best Time to Buy and Sell Stock II (opens new window), we used a greedy strategy to ensure that we collected the positive profit each day, which would eventually lead to the maximum profit.

However, with transaction fees, we need to care about when to buy and sell, as transaction fees might negate any small profits.

Using the greedy approach, the idea is to buy at a low point and sell at a high point only if the profit after fees is still positive.

• Buying date: We record whenever we find a lower price.
• Selling date: It is not necessary to calculate the exact selling date. If the current price is higher than (lowest price + fee), we can collect the profit. The exact selling date is essentially the last day within a profitable range (we don’t need to compute the exact day).

While collecting profit, there are three scenarios:

• Scenario 1: On the day of computing the profit, it might not be the last day of the profitable range (not really selling the stock, as if still holding it), thus further profit can be accumulated.
• Scenario 2: The previous day was the last day in the profitable range (actually sold the stock), and today we need to reset the minimum price.
• Scenario 3: No actions taken, maintaining the existing state (buy, sell, or idle).

The C++ code for the greedy algorithm is as follows:

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int result = 0;
        int minPrice = prices[0]; // Record the lowest price
        for (int i = 1; i < prices.size(); i++) {
            // Scenario 2: which is like buying
            if (prices[i] < minPrice) minPrice = prices[i];

            // Scenario 3: maintaining the existing state (as buying is not cheap, selling results in a loss)
            if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {
                continue;
            }

            // Compute the profit, maybe multiple times, but the last time is the actual selling
            if (prices[i] > minPrice + fee) {
                result += prices[i] - minPrice - fee;
                minPrice = prices[i] - fee; // Scenario 1, this is crucial to avoid double counting of fees
            }
        }
        return result;
    }
};

• Time complexity: O(n)
• Space complexity: O(1)

From the code, you can notice the action for Scenario 1: if you are still in the profitable range, it doesn't mean an actual sale, as profit calculations deduct fees each time. Therefore, set minPrice = prices[i] - fee; to avoid double counting the fee on future profit calculations.

You might notice that the code for Scenario 3 can be omitted for clarity. It was kept for expressiveness.

Dynamic Programming

In the "Code with Carl" public account, we will thoroughly discuss dynamic programming in an upcoming series. Here's my commented C++ code for the solution using dynamic programming. Interested readers can explore it further.

This dynamic programming approach is almost identical to the one in 0122.Best Time to Buy and Sell Stock II (opens new window), except we need to deduct the fee upon selling.

C++ code:

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        // dp[i][1]: the maximum cash held in hand on day i.
        // dp[i][0]: the maximum cash left after holding stock on day i.
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] -= prices[0]; // Holding stock
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};

• Time complexity: O(n)
• Space complexity: O(n)

The space can be optimized because the current state only depends on the previous state.

Here is the optimized C++ code:

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        int holdStock = (-1) * prices[0]; // Holding stock
        int saleStock = 0; // Selling stock
        for (int i = 1; i < n; i++) {
            int previousHoldStock = holdStock;
            holdStock = max(holdStock, saleStock - prices[i]);
            saleStock = max(saleStock, previousHoldStock + prices[i] - fee);
        }
        return saleStock;
    }
};

• Time complexity: O(n)
• Space complexity: O(1)

Summary

The greedy approach for this problem is quite challenging; dynamic programming is a more conventional method. However, understanding both can broaden your problem-solving skills and appreciation of greedy algorithms.

In our future lessons on the stock problem series, we will connect various stock problems using dynamic programming.

Other Language Versions

Java

// Greedy Approach
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int buy = prices[0] + fee;
        int sum = 0;
        for (int p : prices) {
            if (p + fee < buy) {
                buy = p + fee;
            } else if (p > buy){
                sum += p - buy;
                buy = p;
            }
        }
        return sum;
    }
}

class Solution { // Dynamic Programming
    public int maxProfit(int[] prices, int fee) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int[][] dp = new int[prices.length][2];

        // base case
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }

        return dp[prices.length - 1][0];
    }
}

Python

class Solution: # Greedy Approach
    def maxProfit(self, prices: List[int], fee: int) -> int:
        result = 0
        minPrice = prices[0]
        for i in range(1, len(prices)):
            if prices[i] < minPrice: # It's cheaper to buy now
                minPrice = prices[i]
            elif prices[i] > (minPrice + fee): # Profit is made, assume buying high-price stock
                result += prices[i] - (minPrice + fee)
                minPrice = prices[i] - fee
            else: # Prices between minPrice and minPrice + fee, do nothing
                continue
        return result

Go

func maxProfit(prices []int, fee int) int {
    var minBuy int = prices[0] // Buy on the first day
    var res int
    for i := 0; i < len(prices); i++ {
        // If current price is lower than min price, buy here
        if prices[i] < minBuy {
            minBuy = prices[i]
        }
        // If selling at current price is a loss, don't sell, find next sale point
        if prices[i] >= minBuy && prices[i]-fee-minBuy <= 0 {
            continue
        }
        // Ready to sell
        if prices[i] > minBuy+fee {
            // Accumulate daily revenue
            res += prices[i]-minBuy-fee
            // Update minimum value (if still within the profit range, it doesn't mean an actual sale and each calculation must deduct the fee, so `minBuy = prices[i] - fee;` to avoid double counting the fee!)
            minBuy = prices[i]-fee
        }
    }
    return res
}

JavaScript

// Greedy Approach
var maxProfit = function(prices, fee) {
    let result = 0
    let minPrice = prices[0]
    for(let i = 1; i < prices.length; i++) {
        if(prices[i] < minPrice) {
            minPrice = prices[i]
        }
        if(prices[i] >= minPrice && prices[i] <= minPrice + fee) {
            continue
        }

        if(prices[i] > minPrice + fee) {
            result += prices[i] - minPrice - fee
            // Pay the fee only once for buying and selling
            minPrice = prices[i] - fee
        }
    }
    return result
};

// Dynamic Programming
/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    // Rolling array
    // have: maximum profit on the day holding stock
    // notHave: maximum profit on the day not holding stock
    // Include fee in the buying price
    let n = prices.length,
        have = -prices[0]-fee,   // Maximum profit on day 0 holding stock
        notHave = 0;             // Maximum profit on day 0 not holding stock
    for (let i = 1; i < n; i++) {
        // Maximum profit on day i holding stock includes:
        // 1. Holding stock since day i-1, did nothing on day i
        // 2. Not holding stock on day i-1, just bought on day i
        have = Math.max(have, notHave - prices[i] - fee);
        // Maximum profit on day i not holding stock includes:
        // 1. Not holding stock since day i-1, did nothing on day i
        // 2. Holding stock on day i-1, just sold on day i
        notHave = Math.max(notHave, have + prices[i]);
    }
    // Maximum return is when no stock is held at the end
    return notHave;
};

TypeScript

Greedy Approach:

function maxProfit(prices: number[], fee: number): number {
    if (prices.length === 0) return 0;
    let minPrice: number = prices[0];
    let profit: number = 0;
    for (let i = 1, length = prices.length; i < length; i++) {
        if (minPrice > prices[i]) {
            minPrice = prices[i];
        }
        if (minPrice + fee < prices[i]) {
            profit += prices[i] - minPrice - fee;
            minPrice = prices[i] - fee;
        }
    }
    return profit;
};

Dynamic Programming:

function maxProfit(prices: number[], fee: number): number {
    /**
        dp[i][1]: maximum cash on day i without holding stock
        dp[i][0]: maximum cash on day i holding stock
     */
    const length: number = prices.length;
    const dp: number[][] = new Array(length).fill(0).map(_ => []);
    dp[0][1] = 0;
    dp[0][0] = -prices[0];
    for (let i = 1, length = prices.length; i < length; i++) {
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
    }
    return Math.max(dp[length - 1][0], dp[length - 1][1]);
};

Scala

Greedy Approach:

object Solution {
  def maxProfit(prices: Array[Int], fee: Int): Int = {
    var result = 0
    var minPrice = prices(0)
    for (i <- 1 until prices.length) {
      if (prices(i) < minPrice) {
        minPrice = prices(i) // Lower than current lowest price
      }
      if (prices(i) > minPrice + fee) {
        result += prices(i) - minPrice - fee
        minPrice = prices(i) - fee
      }
    }
    result
  }
}