122. Best Time to Buy and Sell Stock II-Greedy Approach(Java, O(n), Med)

• LeetCode 122: Best Time to Buy and Sell Stock II

Problem Overview

LeetCode 122 extends the classic stock trading problem by allowing multiple transactions. Unlike the previous version where you could only buy and sell once, here you can buy and sell the stock multiple times to maximize profit.

Problem Statement

You are given an integer array prices where prices[i] is the price of a given stock on the ith 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 the maximum profit you can achieve.

The Brilliant Greedy Solution

class Solution {
    public int maxProfit(int[] prices) {
        // buy -> (hold or sell based on if it's increasing )
        // sell -> (buy or not buy based on if there is a raise)
        int n = prices.length;
        int profit = 0;
        for (int i = 1; i < n; i++){
            if (prices[i] > prices[i-1]) {
                profit += prices[i] - prices[i-1];
            }
        }
        return profit;
    }
}

Why This Works: The Key Insight 💡

The solution is based on a fundamental insight: To maximize profit with unlimited transactions, you should capture every upward price movement.

The Mathematical Proof

Consider any profitable sequence: Buy at price a, sell at price c where a < b < c

Traditional thinking: profit = c - a

Greedy insight: profit = (b - a) + (c - b) = c - a

The total profit is the same, but the greedy approach is more flexible and captures all opportunities!

Step-by-Step Algorithm Breakdown

Core Logic

if (prices[i] > prices[i-1]) {
    profit += prices[i] - prices[i-1];
}

Translation: If today's price is higher than yesterday's, capture that profit immediately.

What This Represents

Each profitable step represents:

• Buy yesterday at prices[i-1]
• Sell today at prices[i]
• Profit = prices[i] - prices[i-1]

Visual Example Walkthrough

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

Price Chart:
7  ┌─┐
6  │ │           ┌─┐
5  │ │     ┌─┐   │ │
4  │ │     │ │   │ └─┐
3  │ │     │ └─┐ │   │
2  │ │     │   │ │   │
1  │ └─┐   │   │ │   │
0  └───┴───┴───┴─┴───┘
   0 1 2 3 4 5 6 (days)

Day-by-Day Analysis:

Final Result: Maximum profit = 7

Transaction Visualization:

Transactions performed:
1. Buy at price 1 (day 1) → Sell at price 5 (day 2) = +4 profit
2. Buy at price 3 (day 3) → Sell at price 6 (day 4) = +3 profit
Total: 4 + 3 = 7

Why This Greedy Approach is Optimal

1. Captures All Profitable Movements

• Every upward price movement represents a profit opportunity
• By taking all positive differences, we maximize total gains

2. No Missed Opportunities

• If we skip a profitable day, we lose that potential gain forever
• The algorithm ensures no profitable movement is missed

3. Handles Complex Patterns

Consider: [1, 3, 2, 4]

Greedy approach:

• Day 1→2: +2 profit (1→3)
• Day 2→3: 0 profit (3→2, negative)
• Day 3→4: +2 profit (2→4)
• Total: 4

Alternative approach (buy at 1, sell at 4):

• Total: 3

Greedy wins! 🎉

Edge Cases Handled

1. Continuously Declining Prices

prices = [7, 6, 4, 3, 1] → Output: 0

No upward movements = No profit opportunities

2. Continuously Rising Prices

prices = [1, 2, 3, 4, 5] → Output: 4

Every day is profitable: (2-1) + (3-2) + (4-3) + (5-4) = 4

3. Single Day

prices = [1] → Output: 0

No comparison possible = No transactions

Complexity Analysis

Time Complexity: O(n)

• Single pass through the array
• Constant time operations for each element
• Linear scalability with input size

Space Complexity: O(1)

• Only uses a constant amount of extra space
• No additional data structures needed
• Memory efficient regardless of input size

Alternative Approaches Comparison

Common Pitfalls and Mistakes

❌ Mistake 1: Overthinking the Problem

// Don't do this - unnecessarily complex
int buy = -prices[0];
int sell = 0;
for (int i = 1; i < prices.length; i++) {
    buy = Math.max(buy, sell - prices[i]);
    sell = Math.max(sell, buy + prices[i]);
}

❌ Mistake 2: Trying to Track Actual Transactions

// Don't do this - not needed for this problem
List<Integer> buyDays = new ArrayList<>();
List<Integer> sellDays = new ArrayList<>();

✅ Correct Mindset: Focus on Profit Differences

The beauty of this problem is that you don't need to track actual buy/sell days - just capture all positive price movements!

Implementation Variations

Version 1: Enhanced Readability

public int maxProfit(int[] prices) {
    int totalProfit = 0;

    for (int day = 1; day < prices.length; day++) {
        int todayPrice = prices[day];
        int yesterdayPrice = prices[day - 1];

        if (todayPrice > yesterdayPrice) {
            int dailyProfit = todayPrice - yesterdayPrice;
            totalProfit += dailyProfit;
        }
    }

    return totalProfit;
}

Version 2: One-liner (Advanced)

public int maxProfit(int[] prices) {
    return IntStream.range(1, prices.length)
                   .map(i -> Math.max(0, prices[i] - prices[i-1]))
                   .sum();
}

Real-World Application

This algorithm models several real-world scenarios:

• Day trading strategies in financial markets
• Arbitrage opportunities in currency exchange
• Resource allocation in supply chain management
• Dynamic pricing in e-commerce platforms

Key Takeaways

1. Greedy algorithms can be optimal for certain problems
2. Mathematical insight often leads to elegant solutions
3. Simple code doesn't mean simple thinking - this solution required deep understanding
4. Pattern recognition - identifying that profit = sum of all positive differences

Practice Tips

• Try to explain why this greedy approach works to someone else
• Trace through the algorithm with different input examples
• Compare with the single-transaction version (LeetCode 121)
• Consider how this extends to problems with transaction limits