LeetCode 122: Best Time to Buy and Sell Stock II Solution in Python – A Step-by-Step Guide

What Is LeetCode 122: Best Time to Buy and Sell Stock II?

In LeetCode 122: Best Time to Buy and Sell Stock II, you’re given an array prices where prices[i] is the stock price on day i. Your task is to find the maximum profit you can achieve by buying and selling the stock multiple times, with the rule that you must sell before buying again (no holding multiple stocks at once). For example, with prices = [7, 1, 5, 3, 6, 4], the maximum profit is 7 (buy at 1, sell at 5 for 4; buy at 3, sell at 6 for 3).

Problem Statement

• Input: An integer array prices.
• Output: An integer—the maximum profit from multiple buy-sell transactions.
• Rules:
• Buy before sell (sell day > buy day for each transaction).
• Multiple transactions allowed, but only one stock at a time.
• Return 0 if no profit possible.

Constraints

• 1 <= prices.length <= 3 * 10⁴
• 0 <= prices[i] <= 10⁴

Examples

• Input: prices = [7, 1, 5, 3, 6, 4]
• Output: 7
• Why: Buy at 1, sell at 5 (4 profit); buy at 3, sell at 6 (3 profit); total = 7.
• Input: prices = [1, 2, 3, 4, 5]
• Output: 4
• Why: Buy at 1, sell at 5 (4 profit), or sum all increases (1+1+1+1 = 4).
• Input: prices = [7, 6, 4, 3, 1]
• Output: 0
• Why: Prices only decrease, no profit possible.

Understanding the Problem: Capturing Every Gain

To solve LeetCode 122: Best Time to Buy and Sell Stock II in Python, we need to maximize profit by capturing every upward price movement, trading as often as profitable. Unlike LeetCode 121’s single transaction, here we can buy and sell multiple times, making it a game of accumulating all positive differences. A brute force approach—trying every combination of trades—would be overly complex, but the problem’s structure allows simpler solutions. We’ll explore:

• Best Solution (Greedy One-Pass): O(n) time, O(1) space—grabs every profit incrementally.
• Alternative Solution (Peak-Valley): O(n) time, O(1) space—identifies trade points.

Let’s dive into the Best Solution—the greedy one-pass approach—and break it down step-by-step.

Best Solution: Greedy One-Pass Approach

Why This Is the Best Solution

The greedy one-pass approach is the top choice because it’s both fast—O(n) time—and lean—O(1) space—while being incredibly intuitive. It scans the array once, adding every positive price difference to the total profit, effectively “buying” and “selling” at every upward step. It’s like riding every wave in the market, pocketing profit whenever prices rise—simple, efficient, and brilliant!

How It Works

Here’s the strategy:

• Step 1: Initialize Profit:
• Start with max_profit = 0.
• Step 2: Scan Prices:
• For each pair of consecutive days:
• If today’s price is higher than yesterday’s, add the difference to max_profit.
• Step 3: Return the Result:
• max_profit is the total profit from all upward moves.

Why does this work? Since we can buy and sell multiple times, capturing every increase (e.g., 1 to 5 as 1→2→3→4→5) is equivalent to one big trade (1 to 5), but the greedy method ensures we miss no opportunity.

Step-by-Step Example

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

• Initialize: max_profit = 0.
• Day 0 to 1 (7 → 1):
• 1 < 7, no profit, max_profit = 0.
• Day 1 to 2 (1 → 5):
• 5 > 1, profit = 5 - 1 = 4.
• max_profit = 4.
• Day 2 to 3 (5 → 3):
• 3 < 5, no profit, max_profit = 4.
• Day 3 to 4 (3 → 6):
• 6 > 3, profit = 6 - 3 = 3.
• max_profit = 4 + 3 = 7.
• Day 4 to 5 (6 → 4):
• 4 < 6, no profit, max_profit = 7.
• Result: 7.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Step 1: Initialize profit
        max_profit = 0

        # Step 2: Scan consecutive pairs
        for i in range(1, len(prices)):
            # Add profit if price increases
            if prices[i] > prices[i - 1]:
                max_profit += prices[i] - prices[i - 1]

        return max_profit

• Line 4: Start with max_profit = 0.
• Line 7-9: Loop from day 1 to end:
• Line 8-9: If current price exceeds previous, add difference to profit.
• Line 11: Return total profit.
• Time Complexity: O(n)—single pass through array.
• Space Complexity: O(1)—just one variable.

This is a profit-surfing masterpiece!

Alternative Solution: Peak-Valley Approach

Why an Alternative Approach?

The peak-valley approach offers a different angle—still O(n) time and O(1) space. It identifies “valleys” (low points to buy) and “peaks” (high points to sell), summing the profits between them. It’s like charting the stock’s ups and downs, trading at the turning points—visual and insightful, though slightly more complex.

How It Works

Here’s the plan:

• Step 1: Initialize max_profit and pointers.
• Step 2: Find valleys and peaks:
• Valley: Lowest price before an increase.
• Peak: Highest price before a decrease.
• Add peak - valley to profit.
• Step 3: Continue until end of array.

Step-by-Step Example

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

• Initialize: max_profit = 0, i = 0.
• Find Valley:
• 7 > 1, move to 1.
• Valley = 1 (i = 1).
• Find Peak:
• 1 < 5, move to 5.
• 5 > 3, Peak = 5 (i = 2).
• Profit = 5 - 1 = 4, max_profit = 4.
• Next Valley:
• 5 > 3, move to 3.
• Valley = 3 (i = 3).
• Next Peak:
• 3 < 6, move to 6.
• 6 > 4, Peak = 6 (i = 4).
• Profit = 6 - 3 = 3, max_profit = 7.
• End: 6 > 4, no more peaks.
• Result: 7.

Code for Peak-Valley Approach

Copy codeclass Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        i = 0

        while i < len(prices) - 1:
            # Find valley
            while i < len(prices) - 1 and prices[i] >= prices[i + 1]:
                i += 1
            valley = prices[i]

            # Find peak
            while i < len(prices) - 1 and prices[i] <= prices[i + 1]:
                i += 1
            peak = prices[i]

            max_profit += peak - valley

        return max_profit

• Line 4-5: Initialize profit and index.
• Line 7-16: Loop until near end:
• Line 8-10: Find valley by skipping decreases.
• Line 12-14: Find peak by skipping increases.
• Line 16: Add profit from valley to peak.
• Time Complexity: O(n)—each element visited once.
• Space Complexity: O(1)—few variables.

It’s a topographic profit mapper!

Comparing the Two Solutions

• Greedy One-Pass (Best):
• Pros: O(n) time, O(1) space, simple and fast.
• Cons: Less explicit about trades.
• Peak-Valley (Alternative):
• Pros: O(n) time, O(1) space, visual trade points.
• Cons: More complex logic.

Greedy wins for simplicity and speed.

Additional Examples and Edge Cases

• [1]: 0 (no pairs).
• [2, 1]: 0 (no profit).
• [1, 3, 5]: 4 (1 to 5).

Both handle these seamlessly.

Complexity Breakdown

• Greedy: Time O(n), Space O(1).
• Peak-Valley: Time O(n), Space O(1).

Greedy’s elegance shines.

Key Takeaways

• Greedy: Grab every rise!
• Peak-Valley: Trade at turns!
• Profit: Sum all increases.
• Python Tip: Loops are key—see [Python Basics](/python/basics).

Final Thoughts: Ride the Waves

LeetCode 122: Best Time to Buy and Sell Stock II in Python is a profit-chasing thrill. The greedy one-pass approach surfs every gain, while peak-valley maps the trades. Want more stock challenges? Try LeetCode 121: Best Time to Buy and Sell Stock or LeetCode 123: Best Time to Buy and Sell Stock III. Ready to trade? Head to Solve LeetCode 122 on LeetCode and maximize that profit today!