LeetCode 123: Best Time to Buy and Sell Stock III

Problem Restatement

We are given an array prices, where prices[i] is the stock price on day i.

We may complete at most two transactions.

One transaction means:

buy once, then sell once

We cannot hold more than one share at a time, so we must sell before buying again.

We need to return the maximum possible profit.

For example:

prices = [3, 3, 5, 0, 0, 3, 1, 4]

One best strategy is:

buy at 0, sell at 3 -> profit 3
buy at 1, sell at 4 -> profit 3

Total profit:

6

So the answer is:

6

Input and Output

The function shape is:

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

Examples

For:

prices = [3, 3, 5, 0, 0, 3, 1, 4]

A best plan is:

buy at 0
sell at 3
buy at 1
sell at 4

The total profit is:

3 + 3 = 6

So the answer is:

6

For:

prices = [1, 2, 3, 4, 5]

The best profit is made by buying at 1 and selling at 5:

5 - 1 = 4

Even though two transactions are allowed, we do not need to use both.

The answer is:

4

For:

prices = [7, 6, 4, 3, 1]

No profitable transaction exists.

The answer is:

0

First Thought: Split the Problem

With one transaction, we keep the lowest price seen so far.

With two transactions, the best answer can be seen as:

best profit from first transaction
+
best profit from second transaction

But the second transaction must happen after the first transaction is complete.

A direct way is to try every split day:

left side:  best one-transaction profit before or on this day
right side: best one-transaction profit after this day

Then take the best sum.

That works in O(n), but we can compress the idea further.

Key Insight

Track four states while scanning prices:

A buy reduces our balance.

A sell increases our balance.

For each price, update:

buy1 = max(buy1, -price)
sell1 = max(sell1, buy1 + price)
buy2 = max(buy2, sell1 - price)
sell2 = max(sell2, buy2 + price)

The final answer is:

sell2

This also covers using only one transaction, because sell2 can carry forward the best result without forcing a second useful trade.

Algorithm

Initialize:

buy1 = -prices[0]
sell1 = 0
buy2 = -prices[0]
sell2 = 0

Then scan each price.

For every price:

1. Update the best first buy.
2. Update the best first sell.
3. Update the best second buy after the first sell.
4. Update the best second sell.

Return sell2.

Correctness

At every day, buy1 stores the best possible balance after buying once. Since buying at price p gives balance -p, the best first buy is the largest value among all -price values seen so far.

sell1 stores the best profit after completing one transaction. Selling today after the best first buy gives buy1 + price, so taking the maximum keeps the best one-transaction profit.

buy2 stores the best possible balance after completing one transaction and then buying again. If we buy the second stock today, the balance becomes:

sell1 - price

Taking the maximum keeps the best second-buy state.

sell2 stores the best profit after completing at most two transactions. Selling the second stock today gives:

buy2 + price

Taking the maximum keeps the best two-transaction profit.

These four states represent all valid progress stages of at most two transactions, in valid chronological order. Therefore, after all prices are processed, sell2 is the maximum profit possible with at most two transactions.

Complexity

Implementation

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        buy1 = -prices[0]
        sell1 = 0
        buy2 = -prices[0]
        sell2 = 0

        for price in prices:
            buy1 = max(buy1, -price)
            sell1 = max(sell1, buy1 + price)
            buy2 = max(buy2, sell1 - price)
            sell2 = max(sell2, buy2 + price)

        return sell2

Code Explanation

The first buy starts as buying on day 0:

buy1 = -prices[0]

Before selling, profit is zero:

sell1 = 0

The second buy can also start from the first price as a neutral initialization:

buy2 = -prices[0]

The best profit after two sells starts at zero:

sell2 = 0

For each price, update the first buy:

buy1 = max(buy1, -price)

Then update the first sell:

sell1 = max(sell1, buy1 + price)

Then update the second buy:

buy2 = max(buy2, sell1 - price)

Then update the second sell:

sell2 = max(sell2, buy2 + price)

Finally:

return sell2

Testing

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        buy1 = -prices[0]
        sell1 = 0
        buy2 = -prices[0]
        sell2 = 0

        for price in prices:
            buy1 = max(buy1, -price)
            sell1 = max(sell1, buy1 + price)
            buy2 = max(buy2, sell1 - price)
            sell2 = max(sell2, buy2 + price)

        return sell2

def run_tests():
    s = Solution()

    assert s.maxProfit([3, 3, 5, 0, 0, 3, 1, 4]) == 6

    assert s.maxProfit([1, 2, 3, 4, 5]) == 4

    assert s.maxProfit([7, 6, 4, 3, 1]) == 0

    assert s.maxProfit([1]) == 0

    assert s.maxProfit([2, 1, 4, 5, 2, 9, 7]) == 11

    print("all tests passed")

run_tests()

Test meaning: