260. Best Time to Buy and Sell Stock II
🔗 LeetCode Problem: 122. Best Time to Buy and Sell Stock II
📊 Difficulty: Medium
🏷️ Topics: Array, Dynamic Programming, State Machines
📋 Problem Statement
You are given an integer array prices where prices[i] is the price of a given stock on the i-th day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Examples
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
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: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
Constraints
1 <= prices.length <= 3 * 10^40 <= prices[i] <= 10^4
💡 Implication of constraints: - ✅ At least one day of trading (minimum array size 1) - ✅ Can buy and sell multiple times on different days - ✅ Must sell before buying again (hold at most one share) - ✅ Reasonable input size allows O(n) solution
🧒 Understanding The Problem (By Hand)
Let Me Work Example 1 Step By Step
prices = [7, 1, 5, 3, 6, 4]
0 1 2 3 4 5 (day indices)
Rules:
- Can buy and sell multiple times
- Hold at most one stock at a time
- Can buy and sell same day
Let me trace different strategies:
Strategy 1: Single Transaction (like Stock I)
Best buy day = 1 (price=1)
Best sell day = 4 (price=6)
Profit = 6 - 1 = 5
Strategy 2: Multiple Transactions
Transaction 1: Buy day 1 (1), Sell day 2 (5) → Profit = 4
Transaction 2: Buy day 3 (3), Sell day 4 (6) → Profit = 3
Total profit = 4 + 3 = 7 ✓ BETTER!
Strategy 3: Greedy (capture all ups)
Day 0→1: 1-7 = -6 (DOWN, skip)
Day 1→2: 5-1 = +4 (UP, take)
Day 2→3: 3-5 = -2 (DOWN, skip)
Day 3→4: 6-3 = +3 (UP, take)
Day 4→5: 4-6 = -2 (DOWN, skip)
Total = 4 + 3 = 7 ✓ SAME!
What Did I Learn?
Key Insight 1: Multiple transactions can beat single transaction
Key Insight 2: Capture every price increase (greedy works!)
Key Insight 3: Never hold during price decreases
Mathematical Pattern:
Sum of all positive price differences = Maximum profit
[7,1,5,3,6,4] → [+4,+3] = 7
🚫 Approach 1 — Brute Force Recursion
Thought Process
At each day, we have two possible states:
- Can buy (buy = 0): We don't currently hold any stock
- Can sell (buy = 1): We currently hold a stock
For each state, we have choices: 1. When we can buy: Skip buying OR buy the stock 2. When we can sell: Skip selling OR sell the stock
We'll explore all possibilities recursively and take the maximum profit.
Algorithm / Pseudocode
solve(day, canBuy, prices):
if day == n: return 0 // No more days
if canBuy == true: // State: Can buy
skip = solve(day+1, true, prices) // Don't buy, stay ready
buy = -prices[day] + solve(day+1, false, prices) // Buy, now holding
return max(skip, buy)
else: // State: Holding stock
skip = solve(day+1, false, prices) // Keep holding
sell = prices[day] + solve(day+1, true, prices) // Sell, now free
return max(skip, sell)
Code
class Solution {
// Function to find the maximum profit earned using recursion
private int solve(int day, int canBuy, int n, int[] prices) {
// Base case: reached end of array
if (day == n) {
return 0;
}
int profit = 0;
// State: Can buy stock
if (canBuy == 0) {
profit = Math.max(
solve(day + 1, 0, n, prices), // Skip buying
-prices[day] + solve(day + 1, 1, n, prices) // Buy stock
);
}
// State: Holding stock
else {
profit = Math.max(
solve(day + 1, 1, n, prices), // Keep holding
prices[day] + solve(day + 1, 0, n, prices) // Sell stock
);
}
return profit;
}
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
// Start at day 0, can buy (state 0)
return solve(0, 0, n, prices);
}
}
Dry Run
For prices = [7, 1, 5]:
solve(0, 0) → Can buy at day 0 (price=7)
├─ Skip: solve(1, 0)
│ ├─ Skip: solve(2, 0)
│ │ ├─ Skip: solve(3, 0) → 0
│ │ └─ Buy: -5 + solve(3, 1) → -5 + 0 = -5
│ │ → max(0, -5) = 0
│ └─ Buy: -1 + solve(2, 1)
│ ├─ Hold: solve(3, 1) → 0
│ └─ Sell: 5 + solve(3, 0) → 5 + 0 = 5
│ → max(0, 5) = 5
│ → max(0, -1+5) = 4
└─ Buy: -7 + solve(1, 1) → ... (worse options)
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: solve(day, state) returns same value every time
↓
Solution: Store results in dp[day][state] table
Check table before computing
↓
Trade-off: Use O(n) space to achieve O(n) time
Algorithm / Pseudocode
1. Create dp[n][2] initialized with -1
2. Before computing solve(day, state), check if dp[day][state] != -1
3. If already computed, return dp[day][state]
4. Otherwise, compute, store, and return: dp[day][state] = result
Code
class Solution {
// Function to find the maximum profit earned using memoization
private int solve(int day, int canBuy, int n, int[] prices, int[][] dp) {
// Base case
if (day == n) {
return 0;
}
// Check if already computed
if (dp[day][canBuy] != -1) {
return dp[day][canBuy];
}
int profit = 0;
// State: Can buy
if (canBuy == 0) {
profit = Math.max(
solve(day + 1, 0, n, prices, dp),
-prices[day] + solve(day + 1, 1, n, prices, dp)
);
}
// State: Holding
else {
profit = Math.max(
solve(day + 1, 1, n, prices, dp),
prices[day] + solve(day + 1, 0, n, prices, dp)
);
}
// Store and return result
return dp[day][canBuy] = profit;
}
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
// Initialize DP table
int[][] dp = new int[n][2];
for (int[] row : dp) {
Arrays.fill(row, -1);
}
return solve(0, 0, n, prices, dp);
}
}
Dry Run
For prices = [7, 1, 5, 3, 6, 4]:
DP Table Construction:
═══════════════════════════════════════════════════════════════════
Day Price dp[day][0] dp[day][1] Meaning
(canBuy) (holding)
═══════════════════════════════════════════════════════════════════
0 7 7 0 Best from day 0 if can buy
1 1 7 6 Best from day 1 if can buy
2 5 7 6 Best from day 2 if can buy
3 3 3 3 Best from day 3 if can buy
4 6 2 0 Best from day 4 if can buy
5 4 0 0 Best from day 5 if can buy
Answer: dp[0][0] = 7
Time & Space Complexity
⏰ Time: O(n × 2) = O(n) - Each state computed once
💾 Space: O(n × 2) + 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? What should our DP table return?
Let's think about this intuitively:
Step 1: Understanding the "No More Days" Scenario
Imagine: prices = [7, 1, 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?
- If we can buy: No days left to buy and sell → profit = 0
- If we're holding: No days left to sell → stuck with stock → profit = 0
Conclusion: dp[n][0] = dp[n][1] = 0
Step 2: Why This Makes Sense Mathematically
Let me trace what happens in our recursive formula when day = n:
Recursive Logic:
solve(n, canBuy) = ?
From our recursive code:
if (day == n) return 0; ← BASE CASE!
This means:
solve(n, 0) = 0 (no more days to trade)
solve(n, 1) = 0 (no more days to trade)
In tabulation terms:
dp[n][0] = 0
dp[n][1] = 0
Step 3: Working Backwards Logic
Think of DP table as "future profit potential":
dp[day][state] = "Max profit I can get from day `day` onwards in this `state`"
Day n (beyond array): Future profit = 0 ✓
Day n-1: Future profit = best choice today + future from tomorrow
Day n-2: Future profit = best choice today + future from tomorrow
...
Day 0: Future profit = best choice today + future from tomorrow ← ANSWER
Step 4: Visual Understanding
prices = [7, 1, 5] (length n=3)
0 1 2 (valid indices)
DP table needs to handle:
dp[0][state] ← What we want (answer)
dp[1][state]
dp[2][state]
dp[3][state] ← Base case (day beyond array)
Why dp[3] exists?
When we compute dp[2], we need dp[2+1] = dp[3]
When we compute dp[1], we need dp[1+1] = dp[2]
When we compute dp[0], we need dp[0+1] = dp[1]
dp[3] = [0, 0] because no trading possible beyond array!
Step 5: The "Day After Last" Intuition
Real World Analogy:
Last trading day: Friday (day n-1)
Day after: Saturday (day n) → Market closed!
Saturday questions:
"Can I buy today?" → No! Market closed → profit = 0
"Can I sell today?" → No! Market closed → profit = 0
This is why dp[n][0] = dp[n][1] = 0
Algorithm / Pseudocode
1. Create dp[n+1][2] (extra row for base case)
2. Initialize base case: dp[n][0] = dp[n][1] = 0 ("market closed")
3. Iterate from day (n-1) down to 0:
For each canBuy state (0 to 1):
Apply same transition logic as recursion:
- If canBuy: max(skip, buy)
- If holding: max(hold, sell)
4. Return dp[0][0] (max profit starting from day 0, able to buy)
Code
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
// Create DP table with base case
int[][] dp = new int[n + 1][2];
// Base condition: no profit at the end
dp[n][0] = dp[n][1] = 0;
// Fill table from bottom-up
for (int day = n - 1; day >= 0; day--) {
for (int canBuy = 0; canBuy <= 1; canBuy++) {
int profit = 0;
// State: Can buy
if (canBuy == 0) {
profit = Math.max(
dp[day + 1][0], // Skip buying
-prices[day] + dp[day + 1][1] // Buy stock
);
}
// State: Holding
else {
profit = Math.max(
dp[day + 1][1], // Keep holding
prices[day] + dp[day + 1][0] // Sell stock
);
}
dp[day][canBuy] = profit;
}
}
return dp[0][0];
}
}
Dry Run
Building DP table for prices = [7, 1, 5, 3, 6, 4]:
Bottom-Up Table Construction:
═══════════════════════════════════════════════════════════════════
Step 1: Base case (day 6)
dp[6][0] = dp[6][1] = 0
Step 2: Day 5 (price = 4)
canBuy=0: max(dp[6][0], -4 + dp[6][1]) = max(0, -4+0) = 0
canBuy=1: max(dp[6][1], 4 + dp[6][0]) = max(0, 4+0) = 4
Step 3: Day 4 (price = 6)
canBuy=0: max(dp[5][0], -6 + dp[5][1]) = max(0, -6+4) = 0
canBuy=1: max(dp[5][1], 6 + dp[5][0]) = max(4, 6+0) = 6
Step 4: Day 3 (price = 3)
canBuy=0: max(dp[4][0], -3 + dp[4][1]) = max(0, -3+6) = 3
canBuy=1: max(dp[4][1], 3 + dp[4][0]) = max(6, 3+0) = 6
Step 5: Day 2 (price = 5)
canBuy=0: max(dp[3][0], -5 + dp[3][1]) = max(3, -5+6) = 3
canBuy=1: max(dp[3][1], 5 + dp[3][0]) = max(6, 5+3) = 8
Step 6: Day 1 (price = 1)
canBuy=0: max(dp[2][0], -1 + dp[2][1]) = max(3, -1+8) = 7
canBuy=1: max(dp[2][1], 1 + dp[2][0]) = max(8, 1+3) = 8
Step 7: Day 0 (price = 7)
canBuy=0: max(dp[1][0], -7 + dp[1][1]) = max(7, -7+8) = 7 ← ANSWER
═══════════════════════════════════════════════════════════════════
Final Answer: dp[0][0] = 7
Time & Space Complexity
⏰ Time: O(n × 2) = O(n)
💾 Space: O(n × 2) = 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 table
Only need "current" and "next" day values
↓
Optimization: Use 4 variables instead of 2D array
prev[0], prev[1], curr[0], curr[1]
↓
Result: Same time O(n), space reduced to O(1)
Algorithm / Pseudocode
1. Initialize: next_canBuy=0, next_holding=0 (base case)
2. For day from n-1 down to 0:
- curr_canBuy = max(next_canBuy, -price + next_holding)
- curr_holding = max(next_holding, price + next_canBuy)
- Update next values for next iteration
3. Return curr_canBuy
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 next_canBuy = 0, next_holding = 0;
int curr_canBuy = 0, curr_holding = 0;
for (int day = n - 1; day >= 0; day--) {
// Current day: can buy
curr_canBuy = Math.max(next_canBuy, -prices[day] + next_holding);
// Current day: holding
curr_holding = Math.max(next_holding, prices[day] + next_canBuy);
// Update for next iteration
next_canBuy = curr_canBuy;
next_holding = curr_holding;
}
return curr_canBuy;
}
}
Time & Space Complexity
⏰ Time: O(n)
💾 Space: O(1)
Quick Revision
Quick Implementation
public class Solution {
public int maxProfit(int[] a) {
// return recursive(a, 0, 0);
// Integer[][] memo = new Integer[a.length + 1][2];
// return topDown(a, 0, 0, memo);
return bottomUp(a);
}
private int bottomUp(int[] a) {
int n = a.length;
int[][] dp = new int[n + 1][2];
// base case
dp[n][0] = 0;
dp[n][1] = 0;
for (int i = n - 1; i >= 0; i--) {
for (int canBuy = 0; canBuy <= 1; canBuy++) {
int profit = 0;
if (canBuy == 0) {
int skipIt = dp[i + 1][canBuy];
int buyIt = -a[i] + dp[i + 1][1];
profit = Math.max(skipIt, buyIt);
} else {
int skipIt = dp[i + 1][canBuy];
int sellIt = a[i] + dp[i + 1][0];
profit = Math.max(skipIt, sellIt);
}
dp[i][canBuy] = profit;
}
}
// GOTCHA: why dp[0][0]?
// 1. Should be like recursion. So, return with dp[0][canBuy = 0]
// 2. You should not be holding any stock which means dp[0][0]
// You never bought anything yet. That state is physically impossible in the
// problem
return dp[0][0];
}
private int topDown(int[] a, int index, int canBuy, Integer[][] memo) {
if (index == a.length) {
return 0;
}
if (memo[index][canBuy] != null) {
return memo[index][canBuy];
}
int profit = 0;
if (canBuy == 0) {
int skipIt = topDown(a, index + 1, canBuy, memo);
int buyIt = -a[index] + topDown(a, index + 1, 1, memo);
profit = Math.max(skipIt, buyIt);
} else {
int skipIt = topDown(a, index + 1, canBuy, memo);
int sellIt = a[index] + topDown(a, index + 1, 0, memo);
profit = Math.max(skipIt, sellIt);
}
return memo[index][canBuy] = profit;
}
private int recursive(int[] a, int index, int canBuy) {
// step 2: base case
if (index == a.length) {
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);
int buyIt = -a[index] + recursive(a, index + 1, 1);
profit = Math.max(skipIt, buyIt);
} else {
int skipIt = recursive(a, index + 1, canBuy);
int sellIt = a[index] + recursive(a, index + 1, 0);
profit = Math.max(skipIt, sellIt);
}
return profit;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.maxProfit(new int[] { 7, 1, 5, 3, 6, 4 }) == 7);
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 (buy day 1, sell day 2) - 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]→ Return 3 (buy first, sell last) - Monotonic decreasing:
[4, 3, 2, 1]→ Return 0 (never buy)
Test Suite
Basic Tests:
assertEquals(7, maxProfit([7,1,5,3,6,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
Stress Tests:
// Large input with max profit
int[] largeUp = new int[30000];
for(int i = 0; i < 30000; i++) largeUp[i] = i;
assertEquals(29999, maxProfit(largeUp));
// Large input with no profit
int[] largeDown = new int[30000];
for(int i = 0; i < 30000; i++) largeDown[i] = 30000-i;
assertEquals(0, maxProfit(largeDown));
Key Insights
- State modeling: Two states perfectly capture the "hold at most one stock" constraint
- DP progression: Recursion → Memoization → Tabulation → Space optimization
- Greedy connection: This DP approach is mathematically equivalent to summing all positive price differences
- Pattern foundation: This two-state pattern extends to more complex stock problems (cooldown, transaction limits)
The space-optimized solution achieves optimal O(n) time and O(1) space complexity!