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

Problem Restatement

We are given an array prices.

prices[i]

is the price of a stock on day i.

We are also given an integer fee.

We may complete as many transactions as we want, but we cannot hold more than one share at the same time. That means we must sell the current stock before buying again.

Each completed transaction pays the transaction fee once.

Return the maximum profit we can achieve.

The official problem states that the fee is paid once for each buy-sell transaction, and multiple simultaneous transactions are not allowed.

Input and Output

The function shape is:

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        ...

Examples

Example 1:

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

One optimal strategy is:

Total profit:

(8 - 1 - 2) + (9 - 4 - 2) = 8

Output:

8

Example 2:

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

Output:

6

First Thought: Try Every Buy and Sell Choice

A brute force approach is to consider every possible action on every day.

On each day, we can:

1. Do nothing.
2. Buy, if we are not holding a stock.
3. Sell, if we are holding a stock.

This naturally leads to recursion.

The problem is that many states repeat. For example, reaching day i while holding a stock can happen through many different earlier action sequences.

Without memoization, this becomes exponential.

Key Insight

At the end of each day, we only need two states.

Every valid strategy must be in exactly one of these states.

For each price, we update these two values.

If we end the day with no stock, either:

1. We already had no stock.
2. We sell today.

If we end the day holding stock, either:

1. We were already holding.
2. We buy today.

We can charge the fee when selling.

Recurrence

Let price be today’s price.

To update cash:

cash = max(cash, hold + price - fee)

This means:

To update hold:

hold = max(hold, old_cash - price)

This means:

We use old_cash because buying should use the no-stock profit from before today’s update.

Algorithm

1. Set cash = 0.
2. Set hold = -prices[0].
3. For each later price:
   • Save old_cash = cash.
   • Update cash by either keeping cash or selling.
   • Update hold by either keeping hold or buying.
4. Return cash.

The answer is cash because the best final result should not end with an unsold stock. Holding a stock means we paid for it but did not realize its value as profit.

Correctness

We prove that after each day, cash and hold represent the best possible profits for their states.

At the start, before any sale, the best no-stock profit is 0. If we buy on the first day, the best holding profit is -prices[0]. So the initialization is correct.

Assume the values are correct before processing a day with price price.

To end the day with no stock, there are only two possibilities. Either we already had no stock and do nothing, giving profit cash, or we sell the stock we were holding, giving profit hold + price - fee. Taking the maximum gives the best no-stock profit.

To end the day holding stock, there are also only two possibilities. Either we were already holding and do nothing, giving profit hold, or we buy today using a previous no-stock state, giving profit old_cash - price. Taking the maximum gives the best holding profit.

These transitions cover all legal actions and exclude illegal simultaneous transactions because buying is only allowed from the no-stock state and selling is only allowed from the holding state.

Therefore the states remain correct after every day. At the end, the maximum realized profit is cash, so returning it is correct.

Complexity

Let n be the number of days.

Implementation

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        cash = 0
        hold = -prices[0]

        for price in prices[1:]:
            old_cash = cash

            cash = max(cash, hold + price - fee)
            hold = max(hold, old_cash - price)

        return cash

Code Explanation

The no-stock state starts at zero profit:

cash = 0

The holding state starts as if we bought on the first day:

hold = -prices[0]

Before updating cash, save its old value:

old_cash = cash

Then decide whether to sell today:

cash = max(cash, hold + price - fee)

Then decide whether to buy today:

hold = max(hold, old_cash - price)

Finally, return the best profit while holding no stock:

return cash

Alternative Fee Placement

We can also charge the fee when buying instead of selling.

class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        cash = 0
        hold = -prices[0] - fee

        for price in prices[1:]:
            old_cash = cash

            cash = max(cash, hold + price)
            hold = max(hold, old_cash - price - fee)

        return cash

Both versions are correct as long as the fee is charged exactly once per completed transaction.

Example Walkthrough

Use:

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

Initialize:

cash = 0
hold = -1

Process price 3:

cash = max(0, -1 + 3 - 2) = 0
hold = max(-1, 0 - 3) = -1

Process price 2:

cash = max(0, -1 + 2 - 2) = 0
hold = max(-1, 0 - 2) = -1

Process price 8:

cash = max(0, -1 + 8 - 2) = 5
hold = max(-1, 0 - 8) = -1

Process price 4:

cash = max(5, -1 + 4 - 2) = 5
hold = max(-1, 5 - 4) = 1

The hold = 1 state means we have already made profit 5, then bought again at price 4, leaving net profit 1.

Process price 9:

cash = max(5, 1 + 9 - 2) = 8
hold = max(1, 5 - 9) = 1

Final answer:

8

Testing

def test_max_profit_with_fee():
    s = Solution()

    assert s.maxProfit([1, 3, 2, 8, 4, 9], 2) == 8
    assert s.maxProfit([1, 3, 7, 5, 10, 3], 3) == 6
    assert s.maxProfit([1], 0) == 0
    assert s.maxProfit([5, 4, 3, 2, 1], 1) == 0
    assert s.maxProfit([1, 2, 3, 4, 5], 0) == 4
    assert s.maxProfit([1, 4, 6, 2, 8, 3, 10, 14], 3) == 13

    print("all tests passed")

test_max_profit_with_fee()

Test coverage: