LeetCode Problem 714

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Greedy

Solution

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

Problem Understanding

This problem asks us to maximize profit from stock trading over a sequence of days, where each transaction incurs a fixed fee. The input array prices represents the stock price on each day, and fee represents the transaction fee charged for every completed buy-sell transaction.

We are allowed to complete as many transactions as we want, but there is an important restriction: we cannot hold more than one stock at a time. That means before buying again, we must first sell the stock we currently own.

The goal is to compute the maximum possible profit after processing all days.

For example, if prices are [1,3,2,8,4,9] and the fee is 2, one profitable strategy is:

• Buy at 1
• Sell at 8, profit = 8 - 1 - 2 = 5
• Buy at 4
• Sell at 9, profit = 9 - 4 - 2 = 3

Total profit becomes 8.

The constraints are important:

• prices.length can be as large as 5 * 10^4
• Prices and fees can also be large
• A quadratic or exponential solution will not finish in time

These constraints strongly suggest that we need an algorithm close to linear time.

Several edge cases are important:

• A single day means no transaction is possible
• Continuously decreasing prices should produce profit 0
• Very large transaction fees may make trading unprofitable
• Frequent small gains may not be worth taking because of the fee
• Prices can fluctuate heavily, so greedy local decisions must be handled carefully

The problem guarantees valid non-empty input and non-negative fees.

Approaches

Brute Force Approach

A brute force solution would try every possible sequence of buy and sell operations.

At every day, we could make several choices:

• Buy a stock
• Sell a stock
• Skip the day

This creates a decision tree where every state depends on:

• Current day
• Whether we currently hold a stock
• Current accumulated profit

Recursively exploring all possibilities guarantees correctness because every valid transaction sequence is examined.

However, the number of possible states grows exponentially. For each day, multiple branching decisions exist, leading to roughly O(2^n) possibilities in the worst case.

With n up to 50,000, this approach is completely infeasible.

Optimal Dynamic Programming Approach

The key observation is that at any day, we only care about two situations:

1. The maximum profit if we currently do not hold a stock
2. The maximum profit if we currently do hold a stock

We do not need to remember the full transaction history. Only the best achievable profit for these two states matters.

This leads naturally to dynamic programming.

We define:

• cash = maximum profit when not holding a stock
• hold = maximum profit when holding a stock

For each price:

• We can keep our current state
• Or transition between states by buying or selling

This compresses the problem into constant space and linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Explores every possible transaction sequence
Optimal Dynamic Programming	O(n)	O(1)	Tracks only holding and non-holding states

Algorithm Walkthrough

1. Initialize two variables representing the two possible states.

cash represents the maximum profit when we do not currently own a stock.

hold represents the maximum profit when we do own a stock.

Initially:

• cash = 0, because we start with no profit and no stock
• hold = -prices[0], because buying the first stock costs money

2. Iterate through the prices array starting from the second day.

For each price, we consider how the two states can change. 3. Update the cash state.

If we end today without a stock, there are two possibilities:

• We already had no stock yesterday, so profit stays cash
• We sell today, so profit becomes hold + price - fee

Therefore:

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

4. Update the hold state.

If we end today holding a stock, there are two possibilities:

• We already held a stock yesterday
• We buy today using the previous cash

Therefore:

new_hold = max(hold, cash - price)

5. Store the updated values.

We must use temporary variables because both updates depend on the previous day's values. 6. Continue until all days are processed. 7. Return cash.

At the end, the best profit must be in the non-holding state because unsold stock does not count as realized profit.

Why it works

The algorithm maintains a correct invariant throughout execution:

• cash always stores the maximum achievable profit after processing the current day while holding no stock
• hold always stores the maximum achievable profit after processing the current day while holding one stock

Every valid action sequence eventually maps into one of these two states. Since each transition considers all legal possibilities and keeps the best result, the final cash value must be the optimal achievable profit.

Python Solution

from typing import List

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

        for price in prices[1:]:
            new_cash = max(cash, hold + price - fee)
            new_hold = max(hold, cash - price)

            cash = new_cash
            hold = new_hold

        return cash

The implementation directly follows the dynamic programming state transitions.

The variable cash tracks the best profit achievable while not holding a stock. Initially, it is 0 because no transaction has occurred.

The variable hold tracks the best profit achievable while holding a stock. Buying the first stock gives a profit of -prices[0].

For each subsequent price:

• new_cash evaluates whether selling today is better than continuing without a stock
• new_hold evaluates whether buying today is better than continuing to hold

Temporary variables are used because both transitions depend on the previous values of cash and hold.

Finally, the method returns cash, representing the maximum realized profit.

Go Solution

func maxProfit(prices []int, fee int) int {
    cash := 0
    hold := -prices[0]

    for i := 1; i < len(prices); i++ {
        price := prices[i]

        newCash := cash
        if hold+price-fee > newCash {
            newCash = hold + price - fee
        }

        newHold := hold
        if cash-price > newHold {
            newHold = cash - price
        }

        cash = newCash
        hold = newHold
    }

    return cash
}

The Go implementation mirrors the Python logic closely.

Go does not provide a built-in max function for integers, so explicit comparisons are used.

Slices are naturally used for the prices input. Since the problem guarantees at least one element, accessing prices[0] is always safe.

Integer overflow is not a concern because the maximum possible profit remains within Go's standard integer range.

Worked Examples

Example 1

Input:

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

Initial state:

Day	Price	cash	hold
0	1	0	-1

Process remaining days:

Day	Price	new_cash calculation	new_hold calculation	cash	hold
1	3	max(0, -1 + 3 - 2) = 0	max(-1, 0 - 3) = -1	0	-1
2	2	max(0, -1 + 2 - 2) = 0	max(-1, 0 - 2) = -1	0	-1
3	8	max(0, -1 + 8 - 2) = 5	max(-1, 0 - 8) = -1	5	-1
4	4	max(5, -1 + 4 - 2) = 5	max(-1, 5 - 4) = 1	5	1
5	9	max(5, 1 + 9 - 2) = 8	max(1, 5 - 9) = 1	8	1

Final answer:

8

Example 2

Input:

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

Initial state:

Day	Price	cash	hold
0	1	0	-1

Process remaining days:

Day	Price	new_cash calculation	new_hold calculation	cash	hold
1	3	max(0, -1 + 3 - 3) = 0	max(-1, 0 - 3) = -1	0	-1
2	7	max(0, -1 + 7 - 3) = 3	max(-1, 0 - 7) = -1	3	-1
3	5	max(3, -1 + 5 - 3) = 3	max(-1, 3 - 5) = -1	3	-1
4	10	max(3, -1 + 10 - 3) = 6	max(-1, 3 - 10) = -1	6	-1
5	3	max(6, -1 + 3 - 3) = 6	max(-1, 6 - 3) = 3	6	3

Final answer:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each day is processed exactly once
Space	O(1)	Only two state variables are maintained

The algorithm performs a constant amount of work for every price in the array. No nested loops or recursion are used, so the runtime grows linearly with the number of days.

Space usage remains constant because only two variables, cash and hold, are stored regardless of input size.

Test Cases

from typing import List

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

        for price in prices[1:]:
            new_cash = max(cash, hold + price - fee)
            new_hold = max(hold, cash - price)

            cash = new_cash
            hold = new_hold

        return cash

solution = Solution()

assert solution.maxProfit([1,3,2,8,4,9], 2) == 8  # provided example 1
assert solution.maxProfit([1,3,7,5,10,3], 3) == 6  # provided example 2

assert solution.maxProfit([5], 2) == 0  # single day, no transaction possible

assert solution.maxProfit([9,8,7,6,5], 1) == 0  # continuously decreasing prices

assert solution.maxProfit([1,2,3,4,5], 1) == 3  # increasing prices with fee

assert solution.maxProfit([1,4,6,2,8,3,10,14], 3) == 13  # multiple profitable trades

assert solution.maxProfit([1,3,2,5,4,7], 10) == 0  # fee too large to profit

assert solution.maxProfit([1,10], 0) == 9  # zero transaction fee

assert solution.maxProfit([2,2,2,2], 1) == 0  # constant prices

assert solution.maxProfit([1,5,3,8,4,9], 2) == 8  # alternating rises and dips

Test	Why
[1,3,2,8,4,9], fee=2	Validates provided example
[1,3,7,5,10,3], fee=3	Validates second example
[5], fee=2	Tests minimum array size
[9,8,7,6,5], fee=1	Ensures no unnecessary trades
[1,2,3,4,5], fee=1	Tests steadily increasing prices
[1,4,6,2,8,3,10,14], fee=3	Tests multiple optimal transactions
[1,3,2,5,4,7], fee=10	Tests extremely high fee
[1,10], fee=0	Tests zero fee behavior
[2,2,2,2], fee=1	Tests constant prices
[1,5,3,8,4,9], fee=2	Tests repeated buying and selling opportunities

Edge Cases

One important edge case is when the array contains only one price. Since a transaction requires both a buy and a sell, no profit can be made. A naive implementation might incorrectly attempt a transaction or access invalid indices. This solution handles the case naturally because the loop over prices[1:] never executes, and the method correctly returns 0.

Another critical edge case is a strictly decreasing sequence of prices such as [9,8,7,6,5]. Greedy strategies that attempt to trade frequently may accidentally produce negative profit. The dynamic programming transitions prevent this because cash never decreases. Selling is only chosen when it improves profit.

A third important case occurs when the transaction fee is very large. Even if prices rise, the fee may eliminate all gains. For example, with prices [1,3,2,5,4,7] and fee 10, every possible trade results in non-positive profit. The algorithm correctly avoids all transactions because the sell transition never becomes beneficial.

Another subtle edge case involves fluctuating prices where holding longer is more profitable than making multiple small trades. The algorithm naturally handles this because hold and cash always preserve the globally optimal states, not merely locally optimal decisions.