Skip to main content

123. Best Time to Buy and Sell Stock III

hard

Maximize profit with at most two non-overlapping transactions. A four-state DP — buy1, sell1, buy2, sell2 — that compresses to constant space.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete at most two transactions. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Constraints

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^5

Examples

Example 1

Input
prices = [3,3,5,0,0,3,1,4]
Output
6

Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2

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

Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3

Input
prices = [7,6,4,3,1]
Output
0

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Define four states: holding after first buy, in cash after first sell, holding after second buy, in cash after second sell.

Hint 2

Each day update buy1 = max(buy1, -p); sell1 = max(sell1, buy1 + p); buy2 = max(buy2, sell1 - p); sell2 = max(sell2, buy2 + p).

Hint 3

Initialize buy1 = buy2 = -infinity (or -prices[0]) and sell1 = sell2 = 0.

Solution approach

Reveal approach

Four rolling state variables track the best profit reached at each pipeline stage. buy1 = max profit when holding after exactly one buy; sell1 = max profit after closing the first transaction; buy2 = max profit when holding mid-second-transaction; sell2 = max profit after closing the second. Initialize buy1 = buy2 = -infinity (or -prices[0]) and sell1 = sell2 = 0. For each price p: buy1 = max(buy1, -p); sell1 = max(sell1, buy1 + p); buy2 = max(buy2, sell1 - p); sell2 = max(sell2, buy2 + p). The same-day chain works because each next assignment uses the just-updated previous stage — exactly the semantics we want (a buy after sell is allowed on the same day with zero net profit). Return sell2. O(n) time, O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • state-machine

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

More DP 1D practice problems

See all DP 1D problems →