We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Best Time to Buy and Sell Stock with Transaction Fee

Number: 714

Difficulty: Medium

Paid? No

Companies: Amazon, Microsoft, TikTok, Apple, Adobe, Meta, Bloomberg

Problem Description

You are given an array prices where prices[i] is the price of a given stock on the iᵗʰ day, and an integer fee representing a transaction fee. The task is to find the maximum profit you can achieve by performing as many transactions as you like, with the constraint that you have to pay the given fee for each transaction. Note that you cannot have multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Key Insights

  • Use dynamic programming to track profits when holding and not holding the stock.
  • Define two states:
    • cash: maximum profit when you do not hold any stock.
    • hold: maximum profit when you hold a stock.
  • When buying, you update the hold state by subtracting the current price from cash.
  • When selling, add the current price to hold and subtract the fee.
  • Update both states iteratively as you traverse the price list.

Space and Time Complexity

Time Complexity: O(n), where n is the number of days (prices.length).
Space Complexity: O(1), as only two variables (states) are maintained at each iteration.

Solution

We use a dynamic programming approach using two variables: cash and hold.

  • cash represents the maximum profit when no stock is held.
  • hold represents the maximum profit when a stock is held.

Initialize cash = 0 and hold = -prices[0]. Then, for each day, update:

  • cash as the maximum of the previous cash or the profit from selling the stock held (hold + current price - fee).
  • hold as the maximum of the previous hold or the profit from buying the stock (cash - current price).

After processing all days, the maximum profit will be in cash because you must have sold any held stock to realize the profit.

Code Solutions

# Define a function to calculate maximum profit.
def maxProfit(prices, fee):
    # Base case: if prices is empty, profit is 0
    if not prices:
        return 0

    # Initialize cash (profit without stock) and hold (profit with stock)
    cash = 0
    hold = -prices[0]
    
    # Loop through each day's price starting from the second day
    for price in prices[1:]:
        # Temporary variable to hold previous cash value
        prev_cash = cash
        # Update cash. Either you keep your previous cash or sell the stock today.
        cash = max(cash, hold + price - fee)
        # Update hold. Either you keep holding or buy the stock today.
        hold = max(hold, prev_cash - price)
    
    # The maximum profit is when you are not holding any stock.
    return cash

# Example usage:
prices = [1, 3, 2, 8, 4, 9]
fee = 2
print(maxProfit(prices, fee))  # Output: 8
← Back to All Questions