hard

Best Time to Buy and Sell Stock III

Maximize profit across at most two non-overlapping trades.

1. Define the problem

Best Time to Buy and Sell Stock III

You are given an array prices where pricesi is the price of a stock on day i. Find the maximum profit you can achieve. You may complete at most two transactions . You must sell the stock before you buy again, so you can never hold more than one share at a time. A brute-force search over every pair of buy/sell days for two transactions is too slow. Instead, track four running numbers as you scan the prices once: the best profit after one buy, one sell, a second buy, and a second sell . Each of the four updates on a given day only depends on the previous day's numbers, so a single left-to-right pass keeps them all correct. Money from the first sale funds the second buy — that's why buy2 is computed from sell1, not from zero.

Constraints

  • 1 ≤ prices.length ≤ 105
  • 0 ≤ pricesi ≤ 105

Example

Inputprices = [3, 3, 5, 0, 0, 3, 1, 4]
Output6

Explanation Buy on day 3 (price 0), sell on day 5 (price 3), profit 3. Buy on day 6 (price 1), sell on day 7 (price 4), profit 3. Total profit = 3 + 3 = 6.

2. Visualize the solution

The row is the four running best profits, one cell each

The row is the four running best profits, one cell each
Statusinit

day 0, price=3. buy1=-3 (first possible buy). sell1, buy2, sell2 all stay at their starting values. All four cells get their first value here.

What happens in this step

price = 3
buy1 = max(-Infinity, -3) = -3
sell1 = max(0, buy1 + 3 = 0) = 0
buy2 = max(-Infinity, sell1 - 3 = -3) = -3
sell2 = max(0, buy2 + 3 = 0) = 0
Step 1 of 5

Steps to visualize

  1. The row never changes shape: the four cells are buy1, sell1, buy2 and sell2, in that order.
  2. The highlight box covers the cells that changed on the day the step describes.
  3. buy1 tracks the best (most negative) cost of a first purchase seen so far.
  4. sell1 tracks the best profit after selling that first share.
  5. buy2 tracks the best net position after buying a second share, funded by sell1.
  6. sell2 tracks the best profit after selling that second share — the final answer.
  7. On each price, update all four in order: buy1, sell1, buy2, sell2, always taking the better of "do nothing" versus "act today".
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the four running best profits, one cell each
Statusinit

day 0, price=3. buy1=-3 (first possible buy). sell1, buy2, sell2 all stay at their starting values. All four cells get their first value here.

What happens in this step

price = 3
buy1 = max(-Infinity, -3) = -3
sell1 = max(0, buy1 + 3 = 0) = 0
buy2 = max(-Infinity, sell1 - 3 = -3) = -3
sell2 = max(0, buy2 + 3 = 0) = 0
Step 1 of 5
4. Solution

Solution

solution.tsTypeScript
function maxProfit(prices) {
  let buy1 = -Infinity;
  let sell1 = 0;
  let buy2 = -Infinity;
  let sell2 = 0;

  for (const price of prices) {
    buy1 = Math.max(buy1, -price);
    sell1 = Math.max(sell1, buy1 + price);
    buy2 = Math.max(buy2, sell1 - price);
    sell2 = Math.max(sell2, buy2 + price);
  }

  return sell2;
}
Time
O(n)
Space
O(1)
5. Test cases

Test cases

InputExpectedCovers
prices = [3, 3, 5, 0, 0, 3, 1, 4]6example from the docstring
prices = [1]0smallest valid input: a single price, no transaction possible
prices = [7, 6, 4, 3, 1]0prices only fall, so no profitable transaction exists
prices = [1, 2, 3, 4, 5]4a single long rise, where a second transaction adds nothing
prices = [1, 4, 2, 5, 1, 6]9two clearly separated profitable windows worth both transactions
prices = [5, 5, 5, 5]0unchanging prices give no room for profit

Keep reading