LeetCode 122: Best Time to Buy and Sell Stock II - All Solutions Explained

Problem Statement

The Best Time to Buy and Sell Stock II problem, LeetCode 122, is a medium-level challenge that builds on the concept of stock trading. You’re given an array prices where prices[i] represents the stock price on day i. Unlike LeetCode 121, here you can buy and sell multiple times to maximize profit, as long as you sell before buying again. Your goal is to calculate the maximum possible profit from any number of transactions.

Constraints

1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4

Examples

Example 1:

Example in Python

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1), sell on day 3 (price = 5), profit = 4. Buy on day 4 (price = 3), sell on day 5 (price = 6), profit = 3. Total profit = 4 + 3 = 7.

Example 2:

Example in Python

004aad

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1), sell on day 5 (price = 5), profit = 4. Alternatively, sum all daily increases: 1+1+1+1 = 4.

Example 3:

004aad

Example in Python

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: Prices decrease daily—no profit possible.

Understanding the Problem

To solve LeetCode 122, we need to maximize profit by performing multiple buy-sell transactions. Key points:

You can buy and sell as many times as you want, but you must sell before buying again.
Profit is the sum of all positive price differences from valid transactions.
We can capture every upward price movement to maximize profit.

We’ll explore two solutions:

Greedy Approach: Collect profit from every price increase (optimal solution).
Peak-Valley Approach: Identify buy (valley) and sell (peak) points.

Solution 1: Greedy Approach (Best Solution)

Intuition

Since we can buy and sell multiple times, we can greedily collect profit whenever the price increases from one day to the next. Every positive difference contributes to the total profit.

How It Works

Iterate through the array.
For each pair of consecutive days, if the price increases (prices[i] > prices[i-1]), add the difference to the total profit.
Return the accumulated profit.

Step-by-Step Example

For prices = [7,1,5,3,6,4]:

Day 1 to 2: 7 to 1 (no profit, skip).
Day 2 to 3: 1 to 5 (profit = 4).
Day 3 to 4: 5 to 3 (no profit, skip).
Day 4 to 5: 3 to 6 (profit = 3).
Day 5 to 6: 6 to 4 (no profit, skip).
Total profit = 4 + 3 = 7.

004aad Python Code (Greedy Solution)

Example in Python

def maxProfit(prices: list[int]) -&gt; int:
    if not prices or len(prices) &lt; 2:
        return 0
    
    total_profit = 0
    for i in range(1, len(prices)):
        if prices[i] &gt; prices[i-1]:
            total_profit += prices[i] - prices[i-1]
    
    return total_profit

# Test cases
print(maxProfit([7,1,5,3,6,4]))  # Output: 7
print(maxProfit([1,2,3,4,5]))    # Output: 4
print(maxProfit([7,6,4,3,1]))    # Output: 0

Detailed Walkthrough

Edge Case: Empty or single-element array returns 0.
Profit Collection: Add positive differences between consecutive days.
Single Pass: Iterate once, accumulating profit.

Complexity

Time Complexity: O(n), where n is the array length—single pass.
Space Complexity: O(1), uses only a single variable.

Why It’s the Best

Simple and efficient—captures all profit opportunities.
Intuitive for interviews due to its greedy nature.
No need for complex tracking.

Solution 2: Peak-Valley Approach

Intuition

Visualize the price array as a graph. Profit comes from buying at “valleys” (local minima) and selling at “peaks” (local maxima). Sum all peak-valley differences to get the total profit.

How It Works

Iterate through the array.
Find a valley (price stops decreasing), then find the next peak (price stops increasing).
Add the difference (peak - valley) to the profit.
Repeat until the end of the array.

Step-by-Step Example

For prices = [7,1,5,3,6,4]:

Valley 1: 1 (after 7 decreases).
Peak 1: 5 (before 3 decreases).
Profit 1: 5 - 1 = 4.
Valley 2: 3 (after 5 decreases).
Peak 2: 6 (before 4 decreases).
Profit 2: 6 - 3 = 3.
Total profit = 4 + 3 = 7.

Python Code (Peak-Valley Solution)

Example in Python

def maxProfit(prices: list[int]) -&gt; int:
    if not prices or len(prices) &lt; 2:
        return 0
    
    total_profit = 0
    i = 0
    while i &lt; len(prices) - 1:
        # Find valley
        while i &lt; len(prices) - 1 and prices[i] &gt;= prices[i + 1]:
            i += 1
        valley = prices[i]
        
        # Find peak
        while i &lt; len(prices) - 1 and prices[i] &lt;= prices[i + 1]:
            i += 1
        peak = prices[i]
        
        total_profit += peak - valley
    
    return total_profit

# Test cases
print(maxProfit([7,1,5,3,6,4]))  # Output: 7
print(maxProfit([1,2,3,4,5]))    # Output: 4
print(maxProfit([7,6,4,3,1]))    # Output: 0

Detailed Walkthrough

Edge Case: Empty or single-element array returns 0.
Valley Detection: Skip until price stops decreasing.
Peak Detection: Skip until price stops increasing.
Profit Calculation: Add peak-valley difference.

Complexity

Time Complexity: O(n), single pass with multiple steps per iteration.
Space Complexity: O(1), uses minimal variables.

Pros and Cons

Pros: Intuitive visualization of price trends.
Cons: More complex than greedy approach, harder to implement.

Comparison of Solutions

Solution	Time Complexity	Space Complexity	Best Use Case
Greedy	O(n)	O(1)	Efficiency, interviews
Peak-Valley	O(n)	O(1)	Understanding trends

Edge Cases to Consider

Empty Array: prices = [] → 0.
Single Day: prices = [5] → 0 (no transactions).
Flat Prices: prices = [3,3,3] → 0 (no increases).
All Increases: prices = [1,2,3] → 2 (sum of differences).

Final Thoughts

The greedy approach is the standout solution for LeetCode 122—its O(n) time complexity, simplicity, and ability to capture all profit opportunities make it ideal for coding interviews. The peak-valley method offers a different perspective but is less practical due to its complexity. Mastering this problem prepares you for dynamic programming variants like LeetCode 123 or 714!