LeetCode 123 - Best Time to Buy and Sell Stock III

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to determine the maximum profit we can earn from at most two stock transactions given the daily prices of a stock in an array prices. A transaction is defined as buying once and selling once. The key restriction is that you cannot hold more than one stock at a time, so you must sell before buying again.

The input prices is an array of integers, where each integer represents the price of the stock on that day. The output is a single integer representing the maximum profit achievable under the transaction rules.

Constraints indicate that the array can be up to 10^5 elements long, and each price can be up to 10^5. This implies that any solution with O(n^2) time complexity is likely too slow and will exceed time limits.

Important edge cases include:

Monotonically decreasing prices, where no profit is possible.
Monotonically increasing prices, where performing only one transaction could already maximize profit.
Arrays with fewer than 2 prices, where no transactions are possible.

Approaches

Brute Force

The naive approach is to try all possible pairs of transactions. For each possible first transaction (buy on day i, sell on day j), we attempt every possible second transaction on the remaining days. We calculate profits for each combination and return the maximum sum of the two profits.

While correct, this approach is too slow, as it requires iterating over all pairs of days for both transactions. For n days, this results in O(n^3) time complexity, which is impractical for n = 10^5.

Optimal Approach

The key insight is that we can solve this using dynamic programming by keeping track of profits in stages. We can define four variables representing the best state after each possible action:

first_buy - the maximum profit after buying the first stock.
first_sell - the maximum profit after selling the first stock.
second_buy - the maximum profit after buying the second stock (factoring in the first sell).
second_sell - the maximum profit after selling the second stock.

At each day, we update these variables based on whether taking the current action improves profit. This works because the maximum profit at each stage depends only on the previous stage and the current price, making it suitable for linear iteration with O(1) space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Try all pairs of transactions, slow for large n
Optimal	O(n)	O(1)	Track 4 states iteratively, efficient

Algorithm Walkthrough

Initialize four variables to represent the best profit after each action:

first_buy = -infinity (we want to maximize profit after buying, so we store negative price)
first_sell = 0 (no profit yet)
second_buy = -infinity (we want to maximize profit after buying second, factoring in first_sell)
second_sell = 0 (profit after selling second)

Iterate through each price in prices:
Update first_buy as the maximum of itself and negative current price (representing buying first stock today).
Update first_sell as the maximum of itself and profit from selling at current price after first_buy.
Update second_buy as the maximum of itself and first_sell minus current price (buy second stock using first transaction profit).
Update second_sell as the maximum of itself and profit from selling at current price after second_buy.
After iteration, second_sell contains the maximum achievable profit.

Why it works:

This approach maintains an invariant: at any day, each state variable represents the best possible profit achievable after that action. Iteratively updating ensures we consider every day as a potential buy or sell point without double-counting transactions.

Python Solution

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        
        first_buy = float('-inf')
        first_sell = 0
        second_buy = float('-inf')
        second_sell = 0
        
        for price in prices:
            first_buy = max(first_buy, -price)
            first_sell = max(first_sell, first_buy + price)
            second_buy = max(second_buy, first_sell - price)
            second_sell = max(second_sell, second_buy + price)
        
        return second_sell

Implementation Walkthrough:

We start with the initial states representing no transactions. On each day, we update these states to reflect whether buying or selling today improves the profit. first_buy captures the best price to buy the first stock, first_sell captures profit after selling it, second_buy uses the profit from the first transaction to simulate buying again, and second_sell finally captures the maximum total profit.

Go Solution

func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }

    firstBuy, firstSell := -1 << 31, 0
    secondBuy, secondSell := -1 << 31, 0

    for _, price := range prices {
        if -price > firstBuy {
            firstBuy = -price
        }
        if firstBuy+price > firstSell {
            firstSell = firstBuy + price
        }
        if firstSell-price > secondBuy {
            secondBuy = firstSell - price
        }
        if secondBuy+price > secondSell {
            secondSell = secondBuy + price
        }
    }

    return secondSell
}

Go-specific notes:

We use -1 << 31 to simulate negative infinity. Slice iteration is used instead of Python list iteration. All arithmetic operations are safe given the problem constraints. No nil checks are required as an empty slice is handled at the beginning.

Worked Examples

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

Day	Price	first_buy	first_sell	second_buy	second_sell
0	3	-3	0	-3	0
1	3	-3	0	-3	0
2	5	-3	2	-1	2
3	0	0	2	2	2
4	0	0	2	2	2
5	3	0	3	2	5
6	1	0	3	2	5
7	4	0	4	2	6

Maximum profit: 6

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

Day	Price	first_buy	first_sell	second_buy	second_sell
0	1	-1	0	-1	0
1	2	-1	1	-1	1
2	3	-1	2	-1	2
3	4	-1	3	-1	3
4	5	-1	4	-1	4

Maximum profit: 4

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

All transactions are unprofitable. Maximum profit remains 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through prices array, updating 4 variables
Space	O(1)	Only 4 integer variables are maintained, no additional data structures

The linear time complexity is efficient even for the largest allowed input size, and constant space ensures minimal memory usage.

Test Cases

# Basic examples
assert Solution().maxProfit([3,3,5,0,0,3,1,4]) == 6  # Two transactions
assert Solution().maxProfit([1,2,3,4,5]) == 4       # Only one transaction needed
assert Solution().maxProfit([7,6,4,3,1]) == 0       # No profitable transaction

# Edge cases
assert Solution().maxProfit([]) == 0                # Empty list
assert Solution().maxProfit([5]) == 0               # Single element
assert Solution().maxProfit([2,1,2,0,1]) == 2      # Two small transactions

# Large input
assert Solution().maxProfit([i for i in range(100000)]) == 99999  # Increasing sequence

Test	Why
`[3,3,5,0,0,3,1,4]`	Standard case with 2 profitable transactions
`[1,2,3,4,5]`	Monotonically increasing, only one transaction needed
`[7,6,4