Best Time to Buy and Sell Stock II

Difficulty: Medium
Topics: Array, Dynamic Programming, Greedy
Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

Problem Description

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 and return the maximum profit you can achieve.

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.
Total profit is 4.

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 * 104
0 <= prices[i] <= 104

Solution

1. Problem Deconstruction

Technical Restatement:
Given a time-series array prices of length $n$ , determine the maximum achievable profit through a sequence of buy-sell actions under the constraints: (1) Only one share may be held at any time, (2) A sell operation must occur after its corresponding buy operation (though same-day buy-sell is permitted), and (3) An unlimited number of transactions are allowed. Formally, find a set of non-overlapping intervals $[i, j]$ where $i \leq j$ such that the sum $\sum (prices[j] - prices[i])$ is maximized.

Beginner-Friendly Explanation:
Imagine you’re a trader who can buy and sell a stock over several days. You can only own one share at a time, meaning you must sell before buying again (unless you sell on the same day you bought). Your goal is to figure out which days to buy and sell to make the most money. You can make as many trades as you want. Note: Buying low and selling high is the key, but you can’t use future information when making a decision on a given day.

Mathematical Formulation:
Let $p$ be the price array of length $n$ . We seek to maximize:

\sum_{k=1}^{m} (p[s_k] - p[b_k])

where $m$ is the number of transactions, and for each transaction $k$ , the buy day $b_k$ and sell day $s_k$ satisfy $b_k \leq s_k$ and $s_k < b_{k+1}$ (no overlapping holdings). The constraint $s_k < b_{k+1}$ ensures we never hold more than one share. Since same-day transactions are allowed, $b_k = s_k$ is permitted, though such transactions yield zero profit.

Constraint Analysis:

1 <= prices.length <= 3 * 10^4: The upper bound of 30,000 elements necessitates an efficient algorithm, likely $O(n)$ or $O(n \log n)$ . A naive $O(n^2)$ solution would require ~900 million operations in the worst case, which is computationally infeasible.
0 <= prices[i] <= 10^4: Zero prices are allowed. This means a stock can become worthless, which must be handled correctly (e.g., selling at a loss might be necessary if we are holding). However, note that the problem allows not buying at all (profit zero), so we should never end with a net loss. The upper bound of 10,000 per price implies that total profit can be as large as $30,000 \times 10^4 = 3 \times 10^8$ , which fits within a 32-bit integer.

Hidden Edge Cases:

Monotonically decreasing array: Maximum profit is zero (Example 3).
Monotonically increasing array: Buy at first day, sell at last (Example 2).
Flat array: All prices equal, profit is zero (no profitable transactions).
Large fluctuations: Algorithm must capture all incremental gains.
Single-day array: Only one price, cannot complete a buy-sell cycle (profit zero).

2. Intuition Scaffolding

Analogies:

Real-World Metaphor (Hiking): Imagine you are hiking in a mountain range. Each price is an elevation. You want to collect all the “upward elevation gains” during your hike. Every time you ascend from a valley to a peak, you add that height gain to your total. You skip all downhill sections because they represent losses. This sums all positive daily changes.
Gaming Analogy (RPG Item Trading): Think of an RPG where you buy and sell potions in different towns. Each town has a price. You can carry only one potion at a time. Your goal is to maximize gold by buying in cheap towns and selling in expensive ones. You can teleport between towns instantly, so you always know future prices. The optimal strategy is to buy in any town if the next town’s price is higher.
Math Analogy (Difference Array): The problem reduces to analyzing the difference array $d$ where $d[i] = prices[i] - prices[i-1]$ for $i > 0$ . The total profit is the sum of all positive differences. This is because any upward movement can be captured by buying at the start of the rise and selling at the end. Conversely, negative differences are avoided by not holding during declines.

Common Pitfalls:

Single Buy-Sell Fallacy: Trying to find the global minimum and maximum fails because the max might occur before the min (e.g., [3,2,1,5] → min=1, max=5 works, but [5,3,4,1] → min=1, max=5 is invalid since 5 comes before 1).
Peak-Valley Greedy: Without same-day transactions, one might think to always buy at valleys and sell at peaks. This is correct, but requires careful implementation to avoid missing intermediate peaks.
Overcomplication: Attempting dynamic programming with state machines is unnecessary for this variant (though needed for limited transaction problems).
Ignoring Zero-Profit Days: Not buying on a day with zero price change might seem optimal, but if the price remains flat, no profit is lost.
Holding Too Long: Holding through a decline (e.g., buying at 1, then price goes to 3 then back to 2) might tempt one to wait for a higher peak, but the optimal is to sell at 3 and avoid the decline.

3. Approach Encyclopedia

1. Brute Force (Recursive):
Explore all possible sequences of buy-sell actions. At each day, if not holding, we can buy or skip; if holding, we can sell or skip. Since $n$ can be 30,000, this is impractical ( $O(2^n)$ ).

Pseudocode:

function brute_force(prices, day, holding):
    if day == len(prices): return 0
    if holding:
        profit1 = brute_force(prices, day+1, True)   # hold
        profit2 = prices[day] + brute_force(prices, day+1, False) # sell
        return max(profit1, profit2)
    else:
        profit1 = brute_force(prices, day+1, False)   # skip
        profit2 = -prices[day] + brute_force(prices, day+1, True) # buy
        return max(profit1, profit2)

Complexity: Time $O(2^n)$ , space $O(n)$ for recursion depth.

2. Greedy (Peak-Valley):
Identify consecutive valleys and peaks. Buy at every valley and sell at the next peak. Sum all (peak - valley) differences.

Visualization:

prices: [7, 1, 5, 3, 6, 4]
          ↓ (valley at 1)
             ↑ (peak at 5) → profit 4
                ↓ (valley at 3)
                   ↑ (peak at 6) → profit 3
Total: 7

Pseudocode:

valley = prices[0]
peak = prices[0]
profit = 0
i = 0
while i < len(prices)-1:
    while i < len(prices)-1 and prices[i] >= prices[i+1]:
        i += 1
    valley = prices[i]
    while i < len(prices)-1 and prices[i] <= prices[i+1]:
        i += 1
    peak = prices[i]
    profit += (peak - valley)
return profit

Complexity: Time $O(n)$ , space $O(1)$ .

3. Greedy (Simple One-Pass):
Since we can buy and sell on the same day, we can capture every upward price movement. For each day, if today’s price is higher than yesterday’s, add the difference to profit.

Mathematical Insight:
The total profit is $\sum_{i=1}^{n-1} \max(0, prices[i] - prices[i-1])$ .

Visualization:

Day:   0   1   2   3   4   5
Price: 7   1   5   3   6   4
Diff:     -6   4  -2   3  -2
Positive:       4       3
Total: 4+3 = 7

Pseudocode:

profit = 0
for i in range(1, len(prices)):
    if prices[i] > prices[i-1]:
        profit += prices[i] - prices[i-1]
return profit

Complexity Proof:
Time: $O(n)$ since we traverse the list once.
Space: $O(1)$ as we use only constant extra variables.

Why It Works:
Any overall price increase can be broken into daily increments. By capturing every positive daily change, we effectively buy at the start of each uphill run and sell at the end. This is equivalent to the peak-valley method without explicit valley/peak detection.

4. Code Deep Dive

Optimal Solution (One-Pass Greedy):

def maxProfit(prices):
    total_profit = 0
    for i in range(1, len(prices)):
        # If the price increased from yesterday to today, we can capture that gain
        if prices[i] > prices[i-1]:
            total_profit += prices[i] - prices[i-1]
    return total_profit

Line-by-Line Annotations:

Line 1: Function definition.
Line 2: Initialize total_profit to 0. This covers the worst-case scenario (no profitable transactions).
Line 3: Loop from the second day (index 1) to the last day. We compare each day with the previous.
Line 4-5: Check if the price increased. If so, the difference is added to total_profit. This is equivalent to buying at prices[i-1] and selling at prices[i].
Line 6: Return the accumulated profit.

Edge Case Handling:

Example 1 ([7,1,5,3,6,4]):
- i=1: 1<7 → skip
- i=2: 5>1 → add 4
- i=3: 3<5 → skip
- i=4: 6>3 → add 3
- i=5: 4<6 → skip
- Total=7 ✓
Example 2 ([1,2,3,4,5]):
- Each step adds 1: 1+1+1+1=4 ✓
Example 3 ([7,6,4,3,1]):
- All differences negative → no additions → 0 ✓
Flat Array ([5,5,5]):
- No positive differences → 0 ✓
Single Day ([5]):
- Loop runs for i in range(1,1) → no iterations → 0 ✓

5. Complexity War Room

Hardware-Aware Analysis:

The one-pass solution uses $O(1)$ space: only two integer variables (total_profit and loop index i).
For $n=30,000$ , the loop runs 29,999 times. On a modern CPU, each iteration is a compare and an optional add (few cycles). Entire execution takes < 1 ms.
The array itself occupies ~240 KB (30,000 integers × 8 bytes each in Python), which fits in L2/L3 cache, ensuring fast memory access.

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	$O(2^n)$	$O(n)$	7/10	❌ Fails for n>20
Peak-Valley	$O(n)$	$O(1)$	6/10	✅ Acceptable
One-Pass Greedy	$O(n)$	$O(1)$	9/10	✅ Highly Recommended

Why One-Pass Wins:

Simplest code, easiest to explain.
No need to handle multiple loops or state variables.
Clearly derived from mathematical insight.

6. Pro Mode Extras

Variants:

Best Time to Buy and Sell Stock I (LC 121): Only one transaction allowed. Solution: Find max difference such that sell price follows buy price.
Best Time to Buy and Sell Stock III (LC 123): At most two transactions. Requires dynamic programming with state tracking.
Best Time to Buy and Sell Stock IV (LC 188): At most k transactions. DP with 2D state: dp[i][j] where i=day, j=transactions used.
With Cooldown (LC 309): Cannot buy the day after selling. DP with states: hold, sold, rest.
With Transaction Fee (LC 714): Each transaction has a fee. DP with states: cash (not holding), hold.

Interview Cheat Sheet:

First Statement: “This is a greedy problem because we can capture all positive daily price changes.”
Mention Constraints: “Since n can be 30,000, we need an O(n) solution.”
Key Insight: “Total profit is the sum of all positive consecutive differences.”
Edge Cases: “Always test with monotonically increasing, decreasing, and flat arrays.”
Code Tip: “A simple for-loop from index 1 to n-1 suffices.”
Common Mistake: “Avoid holding through declines; take profits immediately on upticks.”

#122 - Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II

Problem Description

Solution

1. Problem Deconstruction

2. Intuition Scaffolding

3. Approach Encyclopedia

4. Code Deep Dive

5. Complexity War Room

6. Pro Mode Extras