LeetCode 714: Best Time to Buy and Sell Stock with Transaction Fee

Problem Description

LeetCode Problem 714

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

Difficulty: Medium

Tags: array, dynamic programming, greedy

Rating: 97.09%

Solution Approach

We’ll use dynamic programming with two states: holding a stock and not holding a stock. For each day, we’ll calculate the maximum profit possible in each state.

State Variables

• hold[i]: Maximum profit on day i if we’re holding a stock
• nothold: Maximum profit on day i if we’re not holding any stock

State Transitions

For each day, we have two decisions:

1. If holding a stock:
   • Keep holding the stock: hold[i-1]
   • Buy a new stock: nothold - prices[i]
2. If not holding a stock:
   • Stay without stock: nothold
   • Sell current stock: hold[i-1] + prices[i] - fee

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        hold = [0] * n
        nothold = 0
        
        # Base case - day 0
        hold[0] = -prices[0]  # Initial purchase
        
        for i in range(1, n):
            # Maximum profit if we're holding a stock
            hold[i] = max(
                hold[i-1],           # Keep holding
                nothold - prices[i]  # Buy new stock
            )
            
            # Maximum profit if we're not holding a stock
            nothold = max(
                nothold,                     # Keep not holding
                hold[i-1] + prices[i] - fee  # Sell stock
            )
            
        return nothold

Example Walkthrough

Let’s walk through Example 1: prices = [1,3,2,8,4,9] with fee = 2

Day-by-Day Analysis:

Day 0 (price = 1):

• hold[0] = -1 (buy stock)
• nothold = 0 (initial state)

Day 1 (price = 3):

• hold[1] = max(-1, 0-3) = -1 (keep holding)
• nothold = max(0, -1+3-2) = 0 (not worth selling)

Day 2 (price = 2):

• hold[2] = max(-1, 0-2) = -1 (keep holding)
• nothold = max(0, -1+2-2) = 0 (not worth selling)

Day 3 (price = 8):

• hold[3] = max(-1, 0-8) = -1 (keep holding)
• nothold = max(0, -1+8-2) = 5 (sell for profit!)

Day 4 (price = 4):

• hold[4] = max(-1, 5-4) = 1 (buy at lower price)
• nothold = max(5, 1+4-2) = 5 (keep not holding)

Day 5 (price = 9):

• hold[5] = max(1, 5-9) = 1 (keep holding)
• nothold = max(5, 1+9-2) = 8 (sell for additional profit)

Final profit: 8

Complexity Analysis

• Time Complexity: $O(n)$ where n is the number of days
• Space Complexity: $O(n)$ for the hold array

Code Optimization

We can optimize the space complexity to $O(1)$ by only keeping track of the previous day’s states:

def maxProfit(self, prices: List[int], fee: int) -> int:
    hold = -prices[0] # Maximum profit if holding stock
    nothold = 0       # Maximum profit if not holding stock
    
    for price in prices[1:]:
        prev_hold = hold
        hold = max(hold, nothold - price)
        nothold = max(nothold, prev_hold + price - fee)
    
    return nothold