Log inSign up
hardLeetCodeNot Started

Best Time to Buy and Sell Stock III

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the i-th 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).

### 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. Total profit is 3 + 3 = 6.

### 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 later.

### Example 3 - Input: prices = [7, 6, 4, 3, 1] - Output: 0 - Explanation: No profitable transactions possible.

Constraints:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand phase-based Dynamic Programming for fixed transaction limits.
  • Derive the 4-state capital machine (buy1, sell1, buy2, sell2).
  • Implement the bidirectional prefix/suffix DP baseline and reduce to O(1) space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Stock trading with an exact upper cap of K=2 transactions.
  • Sequential phases where profit from the first transaction re-funds the second.

Algorithmic Decision Tree:

  • If K=2 -> use 4 rolling state variables.
  • Alternatively -> bidirectional prefix max + suffix max array.

Connected Patterns:

Best Time to Buy and Sell Stock IVTrapping Rain Water (bidirectional)

1. Split Point Enumeration with O(n^2) Check

Intuition

Iterate over every possible split day i (from 0 to n-1). Find the max profit for one transaction in [0..i] and one transaction in [i..n-1].

Algorithm

  1. For each index i from 0 to n-1:
  2. Calculate max profit for single transaction in prices[0..i].
  3. Calculate max profit for single transaction in prices[i..n-1].
  4. Add both profits and update maxTotal.
  5. Return maxTotal.

Split Point Enumeration (O(N^2))

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Sum of two non-overlapping transactions: 2 + 4 = 6
Visual state
Values and pointers at this exact step
table
S
max1 + max2
0
k2
leftProfit2
rightProfit4
total6
Variables at this step
k
2
leftProfit
2
rightProfit
4
total
6
Check / comparison
Split at k=2: [3, 3, 5] and [0, 0, 3, 1, 4]
Decision / next transition
Left max profit = 5 - 3 = 2. Right max profit = 4 - 0 = 4.
Why this step matters

Sum of two non-overlapping transactions: 2 + 4 = 6.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maxProfitBrute(const vector<int>& prices) {
8 int n = prices.size();
9 if (n <= 1) return 0;
10 int maxTotal = 0;
11
12 for (int i = 0; i < n; i++) {
13 // First transaction [0..i]
14 int minP = prices[0], p1 = 0;
15 for (int j = 0; j <= i; j++) {
16 minP = min(minP, prices[j]);
17 p1 = max(p1, prices[j] - minP);
18 }
19 // Second transaction [i..n-1]
20 int minP2 = prices[i], p2 = 0;
21 for (int j = i; j < n; j++) {
22 minP2 = min(minP2, prices[j]);
23 p2 = max(p2, prices[j] - minP2);
24 }
25 maxTotal = max(maxTotal, p1 + p2);
26 }
27 return maxTotal;
28}
29
30int main() {
31 vector<int> prices = {3, 3, 5, 0, 0, 3, 1, 4};
32 cout << "Max Profit (Brute Force): " << maxProfitBrute(prices) << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(1)

2. Bidirectional DP (Prefix + Suffix Profit Arrays)

Intuition

Precompute left_profit[i] (max profit in prices[0..i]) and right_profit[i] (max profit in prices[i..n-1]). The max sum left_profit[i] + right_profit[i] gives the answer in O(n) time.

Algorithm

  1. Create left[n] and right[n] initialized to 0.
  2. Left-to-right pass: maintain minPrice, left[i] = max(left[i-1], prices[i] - minPrice).
  3. Right-to-left pass: maintain maxPrice, right[i] = max(right[i+1], maxPrice - prices[i]).
  4. Find max of left[i] + right[i] across all i.

Bidirectional Prefix and Suffix DP Arrays

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Peak at index 2 is 2 (buy 3, sell 5)
Visual state
Values and pointers at this exact step
table
S
[0,0,2,2,2,3,3,4]
0
leftProfits[0,0,2,2,2,3,3,4]
Variables at this step
leftProfits
[0,0,2,2,2,3,3,4]
Check / comparison
Forward pass: compute leftProfits[i]
Decision / next transition
Tracks max profit achievable using at most 1 transaction ending on or before day i.
Why this step matters

Peak at index 2 is 2 (buy 3, sell 5). Peak at index 7 is 4 (buy 0, sell 4).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maxProfitBidirectional(const vector<int>& prices) {
8 int n = prices.size();
9 if (n <= 1) return 0;
10
11 vector<int> left(n, 0);
12 int minP = prices[0];
13 for (int i = 1; i < n; i++) {
14 minP = min(minP, prices[i]);
15 left[i] = max(left[i - 1], prices[i] - minP);
16 }
17
18 vector<int> right(n, 0);
19 int maxP = prices[n - 1];
20 for (int i = n - 2; i >= 0; i--) {
21 maxP = max(maxP, prices[i]);
22 right[i] = max(right[i + 1], maxP - prices[i]);
23 }
24
25 int maxProfit = 0;
26 for (int i = 0; i < n; i++) {
27 maxProfit = max(maxProfit, left[i] + right[i]);
28 }
29 return maxProfit;
30}
31
32int main() {
33 vector<int> prices = {3, 3, 5, 0, 0, 3, 1, 4};
34 cout << "Max Profit (Bidirectional DP): " << maxProfitBidirectional(prices) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n) for left and right arrays

3. 4-State Machine O(1) Memory DP

Intuition

Track the maximum net balance across four stages: buy1, sell1, buy2, and sell2 in a single forward pass.

Algorithm

  1. Initialize buy1 = -prices[0], sell1 = 0, buy2 = -prices[0], sell2 = 0.
  2. For each price in prices:
  3. buy1 = max(buy1, -price)
  4. sell1 = max(sell1, buy1 + price)
  5. buy2 = max(buy2, sell1 - price)
  6. sell2 = max(sell2, buy2 + price)
  7. Return sell2.

Four-State Machine (O(N) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Single pass dynamic programming state machine
Visual state
Values and pointers at this exact step
table
S
b1:-3, s1:0, b2:-3, s2:0
0
buy1-3
sell10
buy2-3
sell20
Variables at this step
buy1
-3
sell1
0
buy2
-3
sell2
0
Check / comparison
Initialize: buy1 = -prices[0] = -3, sell1 = 0, buy2 = -3, sell2 = 0
Decision / next transition
Represents 4 states: bought 1st, sold 1st, bought 2nd, sold 2nd.
Why this step matters

Single pass dynamic programming state machine.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6using namespace std;
7
8int maxProfitOptimal(const vector<int>& prices) {
9 if (prices.empty()) return 0;
10 int buy1 = -prices[0];
11 int sell1 = 0;
12 int buy2 = -prices[0];
13 int sell2 = 0;
14
15 for (int p : prices) {
16 buy1 = max(buy1, -p);
17 sell1 = max(sell1, buy1 + p);
18 buy2 = max(buy2, sell1 - p);
19 sell2 = max(sell2, buy2 + p);
20 }
21 return sell2;
22}
23
24int main() {
25 vector<int> prices = {3, 3, 5, 0, 0, 3, 1, 4};
26 cout << "Max Profit (Optimal 4-State DP): " << maxProfitOptimal(prices) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Split EnumerationO(n^2)O(1)Iterate all split days i and compute Stock I on left and right.Repeated prefix/suffix scanning
2.Bidirectional DPO(n)O(n)Precompute left[i] and right[i] profit arrays.Array memory
3.4-State MachineOptimalO(n)O(1)Track buy1, sell1, buy2, sell2 rolling balances.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Allowing simultaneous transactions: You cannot buy on day 1 and day 2 before selling.

Pitfall 2:

Setting initial buy1 and buy2 to 0 instead of -prices[0] or -infinity: Buying costs money, so initial balance is negative.

Crucial Edge Cases to Validate:

  • Prices strictly decreasing: Output is 0.
  • Length < 2: Output is 0.
  • Only 1 profitable transaction possible: sell2 will simply equal sell1 (second transaction has 0 profit).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Walk the interviewer through the Bidirectional DP idea first to demonstrate problem decomposition, then introduce the 4-state machine to optimize to O(1) space.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.In the 4-state DP solution, why is buy2 updated using sell1 - p instead of -p?

Back to DSA Sheet