Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

What is this problem about?

The "Best Time to Buy and Sell Stock III interview question" increases the difficulty by adding a transaction limit. You are given an array of prices, but you may complete at most two transactions. Like before, you must sell the stock before you buy again. This constraint makes the simple greedy approach from the previous version unusable.

Why is this asked in interviews?

Companies like Goldman Sachs and Microsoft use the "Best Time to Buy and Sell Stock III coding problem" to test a candidate's mastery of Dynamic Programming. It requires the candidate to maintain multiple states (e.g., first buy, first sell, second buy, second sell) and update them in a single pass. It evaluates "Array interview pattern" and complex state-management skills.

Algorithmic pattern used

This problem is solved using Dynamic Programming (State Machine). We maintain four variables representing the maximum balance at each stage:

1. first_buy: The most money you can have after buying the first stock. (Initially -prices[0]).
2. first_sell: The most money you can have after selling the first stock.
3. second_buy: The most money you can have after buying the second stock.
4. second_sell: The most money you can have after selling the second stock. For each price, we update these greedily:

• 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)

Example explanation

Prices: [3, 3, 5, 0, 0, 3, 1, 4]

• After Day 3 (Price 5): first_buy = -3, first_sell = 2.
• After Day 4 (Price 0): first_buy = 0, first_sell = 2, second_buy = 2.
• After Day 6 (Price 3): first_sell = 3, second_buy = 2, second_sell = 5.
• After Day 8 (Price 4): second_sell = 6. Total Max Profit: 6 (Transaction 1: buy at 0 sell at 3; Transaction 2: buy at 1 sell at 4).

Common mistakes candidates make

• Trying all split points: Calculating the max profit for [0...i] and [i...n] for all $i$ is $O(N^2)$, which is too slow.
• Incorrect initialization: Not setting the "buy" states to negative infinity or the first price, which can lead to errors if the stock only goes down.
• State dependency: Not updating the states in the correct order (though with the max logic, the order within a single day often doesn't break the result).

Interview preparation tip

For problems with "at most K" actions, think about the state machine. Each action (buy/sell) moves you to a new state. This pattern is very common in "Dynamic Programming" interviews at high-frequency trading firms.