122. Best Time to Buy and Sell Stock II

Quick Identifier

• Topic: arrays-hashing
• Pattern: Greedy (Accumulate Positive Deltas)
• Hint: If you can buy and sell as many times as you want, why hold through a dip? Just harvest the profit of every single upward price movement.
• Difficulty: Medium
• Companies: Amazon, Meta, Google, Microsoft, Bloomberg
• LeetCode: 122

Quick Sights

• Time Complexity: O(n). We iterate through the array exactly once, looking at adjacent days.
• Space Complexity: O(1). We only maintain a single integer to sum the total profit.
• Core Mechanism: Iterate from day 1 to the end. For each day, compare its price to the previous day's price. If today's price is higher, add the difference to your totalProfit. If it's lower, ignore it.

Concept Explanation

As a senior engineer, don't let the phrase "unlimited transactions" trick you into writing a massive Dynamic Programming state machine. This is a classic example of a problem where local optimums guarantee the global optimum (a Greedy approach).

1. The Physics of the Chart: Imagine a stock chart as a mountain range. The maximum possible profit is literally just the sum of the vertical heights of all the upward slopes.
2. The "Time-Travel" Trick: The problem states you must sell before you buy again, but allows you to buy and sell on the same day.
   • Suppose prices are [1, 2, 3].
   • Standard way: Buy at 1, hold through 2, sell at 3. Profit = 3 - 1 = 2.
   • Greedy way: Buy at 1, sell at 2 (Profit: 1). Instantly re-buy at 2, sell at 3 (Profit: 1). Total Profit = 1 + 1 = 2.
   • Mathematically, (p3 - p1) is identical to (p3 - p2) + (p2 - p1).
3. The Simplification: Because of this mathematical equivalence, you never actually have to track "when" you bought. You just look at yesterday and today. If today went up, you "harvest" that exact piece of the slope. If today went down, you do nothing.

Diagram

This flowchart outlines the dead-simple greedy logic.

Study Pattern (SDE3+)

• 0–3 min: Confidently declare that this is a Greedy problem, not DP. State the mathematical proof: harvesting every A -> B and B -> C is identical to holding A -> C. By harvesting every positive adjacent delta, you perfectly capture all upward momentum without ever holding during a downward trend.
• Implementation pass: It's literally a single loop starting at index 1, checking if nums[i] > nums[i-1]. If so, add the difference. It takes less than 5 lines of code.
• 5 min extension: What happens if the problem introduces a Transaction Fee? (LeetCode 714). Explain that the Greedy approach instantly shatters. You can no longer conceptually buy and sell on the same day, because each trade eats into your margins. With a fee, you are forced to use a State Machine DP (hold state vs cash state) to decide if a minor dip is worth selling and paying the fee, or if you should just hold through the dip.

Approaches

• Brute force DFS — For every day, branch into "Buy", "Sell", or "Do Nothing". Time: $O(2^n)$. Exponentially slow.
• Dynamic Programming — Track maximum profit ending in a hold state vs a cash state. Time: $O(n)$, Space: $O(n)$ or optimized to $O(1)$. Overkill.
• Greedy Positive Deltas — Time: $O(n)$, Space: $O(1)$. (Always pick this)

Optimal Solution

Go

func maxProfit(prices []int) int {
	totalProfit := 0

	// Start from day 1 and compare with day 0
	for i := 1; i < len(prices); i++ {
		// If today's price is higher than yesterday's, harvest the difference
		if prices[i] > prices[i-1] {
			totalProfit += prices[i] - prices[i-1]
		}
	}

	return totalProfit
}

JavaScript

function maxProfit(prices) {
	let totalProfit = 0;

	// Start from day 1 and compare with day 0
	for (let i = 1; i < prices.length; i++) {
		// If today's price is higher than yesterday's, harvest the difference
		if (prices[i] > prices[i - 1]) {
			totalProfit += prices[i] - prices[i - 1];
		}
	}

	return totalProfit;
}

Walkthrough

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

Output: 7. (Conceptually: Buy at 1, sell at 5. Buy at 3, sell at 6).

Edge Cases

• Strictly decreasing array (e.g., [5, 4, 3, 2, 1]). Deltas are always negative. Safe return 0.
• Strictly increasing array (e.g., [1, 2, 3, 4, 5]). It will harvest 1+1+1+1 = 4, which is identical to 5-1 = 4. Safe return correct total.

Pitfalls

• Trying to track "local minimums" and "local maximums" using complex pointer logic (e.g., advancing a pointer until the price drops, then selling). This is overly complicated, highly prone to out-of-bounds errors, and logically identical to just grabbing the daily deltas. Keep it simple.

Similar Problems

• 121. Best Time to Buy and Sell Stock — The single transaction variant.
• 714. Best Time to Buy and Sell Stock with Transaction Fee — The DP variant where Greedy fails.
• 309. Best Time to Buy and Sell Stock with Cooldown — Another DP variant involving a cooldown day.

Mind-Map Tags

#arrays #greedy #adjacent-delta #accumulation #stock