262. Best Time to Buy and Sell Stock III
🔗 LeetCode Problem: 123. Best Time to Buy and Sell Stock III
📊 Difficulty: Hard
🏷️ Topics: Array, Dynamic Programming, State Machines
📋 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).
Examples
Example 1:
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 1 (price = 3) and sell on day 2 (price = 5), profit = 5-3 = 2.
Then buy on day 3 (price = 0) and sell on day 7 (price = 4), profit = 4-0 = 4.
Total profit is 2 + 4 = 6.
Note that you may not buy on day 3 and sell on day 6, and then buy on day 5 and sell on day 4,
as you are engaging multiple transactions at the same time. You must sell before buying again.
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
Explanation: In this case, no transaction is done and max profit = 0.
Constraints
1 <= prices.length <= 10^50 <= prices[i] <= 10^5
💡 Implication of constraints: - ✅ At least one day of trading (minimum array size 1) - ✅ Can complete at most 2 complete transactions (buy + sell = 1 transaction) - ✅ Must sell before buying again (hold at most one share) - ✅ Large input size requires efficient O(n) solution
🧒 Understanding The Problem (By Hand)
Let Me Work Example 1 Step By Step
prices = [3, 3, 5, 0, 0, 3, 1, 4]
0 1 2 3 4 5 6 7 (day indices)
Rules:
- Complete at most 2 transactions
- 1 transaction = buy + sell
- Must sell before buying again
- Can use fewer than 2 transactions
Let me trace different strategies:
Strategy 1: Single Transaction (like Stock I)
Best buy day = 4 (price=0)
Best sell day = 7 (price=4)
Profit = 4 - 0 = 4
Strategy 2: Two Transactions - Optimal Split
Transaction 1: Buy day 4 (0), Sell day 6 (1) → Profit = 1
Transaction 2: Buy day 6 (1), Sell day 7 (4) → Profit = 3
Total profit = 1 + 3 = 4... wait, that's same as single!
Strategy 3: Better Two Transactions
Transaction 1: Buy day 1 (3), Sell day 2 (5) → Profit = 2
Transaction 2: Buy day 4 (0), Sell day 7 (4) → Profit = 4
Total profit = 2 + 4 = 6 ✓ BETTER!
What Did I Learn?
Key Insight 1: Two transactions can beat single transaction
Key Insight 2: Need to track remaining transaction capacity
Key Insight 3: Can use fewer than 2 transactions if more profitable
Mathematical Pattern:
Find optimal split point to divide array into two parts
Maximize: profit[0...k] + profit[k+1...n-1]
But this requires considering all possible combinations!
🚫 Approach 1 — Brute Force Recursion
Thought Process
At each day, we have three pieces of state:
- Day index (
ind): Current position in prices array - Can buy (
buy): Whether we can buy (0) or must sell (1) - Capacity (
cap): Number of transactions remaining (0, 1, or 2)
For each state, we have choices:
- When we can buy: Skip buying OR buy the stock
- When we can sell: Skip selling OR sell the stock (decreases capacity)
We'll explore all possibilities recursively and take the maximum profit.
Algorithm / Pseudocode
solve(day, canBuy, capacity, prices):
if day == n OR capacity == 0: return 0 // No more days or transactions
if canBuy == 0: // State: Can buy
skip = solve(day+1, 0, capacity, prices) // Don't buy, stay ready
buy = -prices[day] + solve(day+1, 1, capacity, prices) // Buy, now holding
return max(skip, buy)
else: // State: Holding stock
skip = solve(day+1, 1, capacity, prices) // Keep holding
sell = prices[day] + solve(day+1, 0, capacity-1, prices) // Sell, complete transaction
return max(skip, sell)
Code
class Solution {
// Function to find the maximum profit earned using recursion
private int func(int ind, int buy, int cap, int n, int[] arr) {
// Base case
if (ind == n || cap == 0) {
return 0;
}
int profit = 0;
// We can buy the stock
if (buy == 0) {
profit = Math.max(
0 + func(ind + 1, 0, cap, n, arr), // Skip buying
(-1) * arr[ind] + func(ind + 1, 1, cap, n, arr) // Buy stock
);
}
// We can sell the stock
if (buy == 1) {
profit = Math.max(
0 + func(ind + 1, 1, cap, n, arr), // Keep holding
arr[ind] + func(ind + 1, 0, cap - 1, n, arr) // Sell stock (complete transaction)
);
}
return profit;
}
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
// Start at day 0, can buy (state 0), with capacity 2
return func(0, 0, 2, n, prices);
}
}
Dry Run
For prices = [3, 3, 5] with capacity = 2:
func(0, 0, 2) → Can buy at day 0 (price=3)
├─ Skip: func(1, 0, 2)
│ ├─ Skip: func(2, 0, 2)
│ │ ├─ Skip: func(3, 0, 2) → 0
│ │ └─ Buy: -5 + func(3, 1, 2) → -5 + 0 = -5
│ │ → max(0, -5) = 0
│ └─ Buy: -3 + func(2, 1, 2)
│ ├─ Hold: func(3, 1, 2) → 0
│ └─ Sell: 5 + func(3, 0, 1) → 5 + 0 = 5
│ → max(0, 5) = 5
│ → max(0, -3+5) = 2
└─ Buy: -3 + func(1, 1, 2) → ... (similar analysis)
This creates exponential tree with overlapping subproblems...
Time & Space Complexity
⏰ Time: O(2^n) - Each call branches into 2 possibilities
💾 Space: O(n) - Recursion depth
This approach has exponential time complexity due to overlapping subproblems.
⚠️ Approach 2 — Memoization (Top-Down DP)
Thought Process (How did you arrive here)
🎯 The Optimization Insight:
Brute Force Problem: Same subproblems solved repeatedly
↓
Key Observation: func(day, buy, cap) returns same value every time
↓
Solution: Store results in dp[day][buy][cap] table
Check table before computing
↓
Trade-off: Use O(n × 2 × 3) space to achieve O(n × 2 × 3) time
Algorithm / Pseudocode
1. Create dp[n][2][3] initialized with -1
2. Before computing func(day, buy, cap), check if dp[day][buy][cap] != -1
3. If already computed, return dp[day][buy][cap]
4. Otherwise, compute, store, and return: dp[day][buy][cap] = result
Code
class Solution {
// Function to find the maximum profit earned using memoization
private int func(int ind, int buy, int cap, int n, int[] arr, int[][][] dp) {
// Base case
if (ind == n || cap == 0) {
return 0;
}
// If the result for this state has already been calculated, return it
if (dp[ind][buy][cap] != -1) {
return dp[ind][buy][cap];
}
int profit = 0;
// We can buy the stock
if (buy == 0) {
profit = Math.max(
0 + func(ind + 1, 0, cap, n, arr, dp),
(-1) * arr[ind] + func(ind + 1, 1, cap, n, arr, dp)
);
}
// We can sell the stock
if (buy == 1) {
profit = Math.max(
0 + func(ind + 1, 1, cap, n, arr, dp),
arr[ind] + func(ind + 1, 0, cap - 1, n, arr, dp)
);
}
// Store the value in dp array and return the calculated profit
return dp[ind][buy][cap] = profit;
}
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
// Declare a DP table to memoize results
int[][][] dp = new int[n][2][3];
// Initialize the dp array with -1
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2; j++) {
Arrays.fill(dp[i][j], -1);
}
}
return func(0, 0, 2, n, prices, dp);
}
}
Dry Run
For prices = [3, 3, 5, 0, 0, 3, 1, 4]:
3D DP Table Construction:
══════════════════════════════════════════════════════════════════════════════════════════
Day Price dp[day][0][2] dp[day][1][2] dp[day][0][1] dp[day][1][1] Meaning
(canBuy,cap2) (holding,cap2) (canBuy,cap1) (holding,cap1)
══════════════════════════════════════════════════════════════════════════════════════════
0 3 6 3 4 4 Best from day 0
1 3 6 5 4 4 Best from day 1
2 5 6 5 4 4 Best from day 2
3 0 6 4 4 4 Best from day 3
4 0 4 4 4 4 Best from day 4
5 3 3 3 3 1 Best from day 5
6 1 3 0 3 0 Best from day 6
7 4 0 0 0 0 Best from day 7
Answer: dp[0][0][2] = 6
Time & Space Complexity
⏰ Time: O(n × 2 × 3) = O(n) - Each state computed once
💾 Space: O(n × 2 × 3) + O(n) = O(n) - DP table + recursion stack
✅ Approach 3 — Tabulation (Bottom-Up DP)
Thought Process (How did you arrive here)
💡 Eliminating Recursion:
Memoization Limitation: Still uses O(n) recursion stack
↓
Key Insight: Fill DP table iteratively from end to start
Eliminate recursion overhead
↓
Algorithm: Start from base case, work towards answer
dp[day] depends only on dp[day+1]
↓
Result: Same time complexity, cleaner implementation
Base Case Derivation (Step by Step)
🤔 The Big Question: What happens when we've processed all days OR used all transactions?
Let's think about this intuitively:
Step 1: Understanding the "No More Days" Scenario
Imagine: prices = [3, 3, 5] and we're at day 3 (beyond last day)
Question: If there are no more days left, what's the maximum profit?
Answer: 0! We can't make any more moves.
Why 0 regardless of our state or remaining capacity?
- No days left to trade → profit = 0
Conclusion: dp[n][buy][cap] = 0 for all buy and cap values
Step 2: Understanding the "No More Transactions" Scenario
Imagine: We're at day 2 but capacity = 0 (no transactions left)
Question: If we have no transaction capacity left, what's the maximum profit?
Answer: 0! We can't buy or complete any more transactions.
Why 0 regardless of current state?
- Can't buy: No capacity to complete transaction → profit = 0
- Holding stock: No capacity to sell → stuck → profit = 0
Conclusion: dp[day][buy][0] = 0 for all day and buy values
Step 3: Base Case in Code
From our recursive logic:
if (ind == n || cap == 0) return 0; ← BASE CASE!
This means:
dp[n][buy][cap] = 0 for all buy, cap
dp[day][buy][0] = 0 for all day, buy
In tabulation:
Initialize all dp[n][buy][cap] = 0
All dp[day][buy][0] are automatically 0 (default initialization)
Algorithm / Pseudocode
1. Create dp[n+1][2][3] (extra row for base case)
2. Initialize base case: dp[n][buy][cap] = 0 for all buy, cap
3. Iterate from day (n-1) down to 0:
For each buy state (0 to 1):
For each capacity (1 to 2):
Apply same transition logic as recursion:
- If canBuy: max(skip, buy)
- If holding: max(hold, sell and reduce capacity)
4. Return dp[0][0][2] (max profit starting from day 0, able to buy, with 2 transactions)
Code
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
// Declaring a 3D DP array of size [n+1][2][3] initialized to 0
int[][][] dp = new int[n + 1][2][3];
// Base case: dp array is already initialized to 0, covering the base case.
// Iterate backwards through the prices array
for (int ind = n - 1; ind >= 0; ind--) {
// buy can be 0 (buying) or 1 (selling)
for (int buy = 0; buy <= 1; buy++) {
// cap represents the number of transactions remaining (can be 1 or 2)
for (int cap = 1; cap <= 2; cap++) {
int profit = 0;
// We can buy the stock
if (buy == 0) {
profit = Math.max(
0 + dp[ind + 1][0][cap], // Skip buying
(-1) * prices[ind] + dp[ind + 1][1][cap] // Buy stock
);
}
// We can sell the stock
if (buy == 1) {
profit = Math.max(
0 + dp[ind + 1][1][cap], // Keep holding
prices[ind] + dp[ind + 1][0][cap - 1] // Sell stock (complete transaction)
);
}
dp[ind][buy][cap] = profit;
}
}
}
// The result is stored in dp[0][0][2] which represents maximum profit after the final transaction.
return dp[0][0][2];
}
}
Dry Run
Building DP table for prices = [3, 3, 5, 0, 0, 3, 1, 4]:
Bottom-Up 3D Table Construction:
═══════════════════════════════════════════════════════════════════
Step 1: Base case (day 8)
dp[8][buy][cap] = 0 for all buy, cap
Step 2: Day 7 (price = 4)
buy=0, cap=2: max(dp[8][0][2], -4 + dp[8][1][2]) = max(0, -4+0) = 0
buy=0, cap=1: max(dp[8][0][1], -4 + dp[8][1][1]) = max(0, -4+0) = 0
buy=1, cap=2: max(dp[8][1][2], 4 + dp[8][0][1]) = max(0, 4+0) = 4
buy=1, cap=1: max(dp[8][1][1], 4 + dp[8][0][0]) = max(0, 4+0) = 4
Step 3: Day 6 (price = 1)
buy=0, cap=2: max(dp[7][0][2], -1 + dp[7][1][2]) = max(0, -1+4) = 3
buy=0, cap=1: max(dp[7][0][1], -1 + dp[7][1][1]) = max(0, -1+4) = 3
buy=1, cap=2: max(dp[7][1][2], 1 + dp[7][0][1]) = max(4, 1+0) = 4
buy=1, cap=1: max(dp[7][1][1], 1 + dp[7][0][0]) = max(4, 1+0) = 4
Step 4: Day 5 (price = 3)
buy=0, cap=2: max(dp[6][0][2], -3 + dp[6][1][2]) = max(3, -3+4) = 3
buy=0, cap=1: max(dp[6][0][1], -3 + dp[6][1][1]) = max(3, -3+4) = 3
buy=1, cap=2: max(dp[6][1][2], 3 + dp[6][0][1]) = max(4, 3+3) = 6
buy=1, cap=1: max(dp[6][1][1], 3 + dp[6][0][0]) = max(4, 3+0) = 4
Continue this pattern...
Final Answer: dp[0][0][2] = 6
Time & Space Complexity
⏰ Time: O(n × 2 × 3) = O(n)
💾 Space: O(n × 2 × 3) = O(n)
🎯 Approach 4 — Space Optimized (Final)
Thought Process (How did you arrive here)
🚀 Ultimate Optimization:
Tabulation Observation: dp[day] only depends on dp[day+1]
↓
Space Insight: Don't need entire n×2×3 table
Only need "current" and "next" day values
↓
Optimization: Use 2D arrays for current and next
after[buy][cap], ahead[buy][cap]
↓
Result: Same time O(n), space reduced to O(1) since 2×3 is constant
Algorithm / Pseudocode
1. Initialize: after[buy][cap] = 0 for all buy, cap (base case)
2. For day from n-1 down to 0:
- For each buy state and capacity:
- Apply DP transition logic
- Store result in ahead[buy][cap]
- Copy ahead to after for next iteration
3. Return ahead[0][2]
Code
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
// Space optimization: only need next day's values
int[][] after = new int[2][3]; // after[buy][cap]
int[][] ahead = new int[2][3]; // current computation
// Base case: already initialized to 0
for (int ind = n - 1; ind >= 0; ind--) {
for (int buy = 0; buy <= 1; buy++) {
for (int cap = 1; cap <= 2; cap++) {
int profit = 0;
if (buy == 0) { // Can buy
profit = Math.max(
after[0][cap], // Skip buying
-prices[ind] + after[1][cap] // Buy stock
);
} else { // Holding stock
profit = Math.max(
after[1][cap], // Keep holding
prices[ind] + after[0][cap - 1] // Sell stock
);
}
ahead[buy][cap] = profit;
}
}
// Copy ahead to after for next iteration
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
after[i][j] = ahead[i][j];
}
}
}
return after[0][2];
}
}
Time & Space Complexity
⏰ Time: O(n × 2 × 3) = O(n)
💾 Space: O(2 × 3) = O(1)
Quick Revision
Quick Implementation
public class Solution {
public int maxProfit(int[] a) {
// return recursive(a, 0, 0, 2);
// Integer[][][] memo = new Integer[a.length + 1][2][3];
// return topDown(a, 0, 0, 2, memo);
return bottomUp(a);
}
private int bottomUp(int[] a) {
int n = a.length;
int[][][] dp = new int[n + 1][2][3];
// Why i will start from n-1 and k starts after 0?
// Because these are base cases in recursion and top-down
// if (index == a.length || k == 0) { return 0; }
// i = n and k = 0 already calculated as 0
for (int i = n - 1; i >= 0; i--) {
for (int canBuy = 0; canBuy <= 1; canBuy++) {
for (int k = 1; k <= 2; k++) {
int profit = 0;
if (canBuy == 0) {
int skipIt = dp[i + 1][canBuy][k];
int buyIt = -a[i] + dp[i + 1][1][k];
profit = Math.max(skipIt, buyIt);
} else {
int skipIt = dp[i + 1][canBuy][k];
int sellIt = a[i] + dp[i + 1][0][k - 1];
profit = Math.max(skipIt, sellIt);
}
dp[i][canBuy][k] = profit;
}
}
}
return dp[0][0][2];
}
private int topDown(int[] a, int index, int canBuy, int k, Integer[][][] memo) {
if (index == a.length || k == 0) {
return 0;
}
if (memo[index][canBuy][k] != null) {
return memo[index][canBuy][k];
}
int profit = 0;
if (canBuy == 0) {
int skipIt = topDown(a, index + 1, canBuy, k, memo);
int buyIt = -a[index] + topDown(a, index + 1, 1, k, memo);
profit = Math.max(skipIt, buyIt);
} else {
int skipIt = topDown(a, index + 1, canBuy, k, memo);
int sellIt = a[index] + topDown(a, index + 1, 0, k - 1, memo);
profit = Math.max(skipIt, sellIt);
}
return memo[index][canBuy][k] = profit;
}
private int recursive(int[] a, int index, int canBuy, int k) {
// step 2: base case
if (index == a.length || k == 0) {
return 0;
}
int profit = 0;
// step 1: canBuy = 0 or 1
// 0 means we can buy (not mandatory. can skip also)
// 1 means we can sell (not mandatory. can skip also)
if (canBuy == 0) {
int skipIt = recursive(a, index + 1, canBuy, k);
int buyIt = -a[index] + recursive(a, index + 1, 1, k);
profit = Math.max(skipIt, buyIt);
} else {
int skipIt = recursive(a, index + 1, canBuy, k);
int sellIt = a[index] + recursive(a, index + 1, 0, k - 1);
profit = Math.max(skipIt, sellIt);
}
return profit;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.maxProfit(new int[] { 3, 3, 5, 0, 0, 3, 1, 4 }) == 6);
System.out.println(s.maxProfit(new int[] { 1, 2, 3, 4, 5 }) == 4);
System.out.println(s.maxProfit(new int[] { 7, 6, 4, 3, 1 }) == 0);
}
}
📝 Edge Cases & Testing
Edge Cases
- Single day:
[5]→ Return 0 (can't buy and sell for profit) - Two days increasing:
[1, 5]→ Return 4 (single transaction optimal) - Two days decreasing:
[5, 1]→ Return 0 (don't buy at all) - All same prices:
[3, 3, 3]→ Return 0 (no profit opportunity) - Monotonic increasing:
[1, 2, 3, 4, 5]→ Return 4 (single transaction optimal) - Monotonic decreasing:
[5, 4, 3, 2, 1]→ Return 0 (never buy)
Test Suite
Basic Tests:
assertEquals(6, maxProfit([3,3,5,0,0,3,1,4])); // Example 1
assertEquals(4, maxProfit([1,2,3,4,5])); // Example 2
assertEquals(0, maxProfit([7,6,4,3,1])); // Example 3
Edge Tests:
assertEquals(0, maxProfit([5])); // Single element
assertEquals(4, maxProfit([1,5])); // Two elements up
assertEquals(0, maxProfit([5,1])); // Two elements down
assertEquals(0, maxProfit([3,3,3,3])); // All same
Transaction Limit Tests:
assertEquals(7, maxProfit([1,2,4,2,5,7,2,4,9,0])); // Multiple peaks, use 2 best
assertEquals(2, maxProfit([2,1,2,0,1])); // Small profits, combine optimally
assertEquals(6, maxProfit([6,1,3,2,4,7])); // Mixed trends
Stress Tests:
// Large input with max profit using 2 transactions
int[] large = {1, 10, 5, 15, 3, 20}; // Two clear profitable segments
assertEquals(27, maxProfit(large)); // (10-1) + (20-3) = 9 + 17 = 26... check manually
// Large input with no profit
int[] largeDown = new int[10000];
for(int i = 0; i < 10000; i++) largeDown[i] = 10000-i;
assertEquals(0, maxProfit(largeDown));
Key Insights
- State modeling: Three dimensions capture transaction capacity constraint perfectly
- DP progression: Classic recursion → memoization → tabulation → space optimization
- Constraint handling: Transaction capacity decreases only on sell (completing a transaction)
- Optimization potential: Can use fewer than 2 transactions if more profitable
- Pattern extension: This 3D DP pattern extends to arbitrary transaction limits (k transactions)
Comparison with Stock II
| Aspect | Stock II (Unlimited) | Stock III (2 Transactions) |
|---|---|---|
| State Space | 2D: [day][buy] | 3D: [day][buy][capacity] |
| Complexity | O(n) time, O(1) space | O(n) time, O(1) space |
| Key Constraint | Hold at most 1 stock | At most 2 transactions |
| Greedy Solution | ✅ Sum positive diffs | ❌ Need DP |
The space-optimized solution achieves optimal O(n) time and O(1) space complexity while handling the complex constraint of at most 2 transactions!