🚀 Try This Problem First!

Before reading the solution, attempt it yourself on LeetCode — you'll retain the concept far better.

🔗 Problem Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

Understanding the Problem

You are given an array prices where prices[i] is the stock price on day i. Unlike the classic version, here you can make as many transactions as you want — but you can only hold one share at a time. You may buy and sell on the same day.

Goal: Return the maximum total profit achievable.

Key Rules:

1. You can buy and sell multiple times.
2. You cannot hold more than one share at a time — you must sell before buying again.
3. If no profit is possible, return 0.

Constraints:

1. 1 ≤ prices.length ≤ 3 × 10⁴
2. 0 ≤ prices[i] ≤ 10⁴

How This Differs From LeetCode 121 #

In LeetCode 121, you were limited to exactly one buy-sell transaction. Here, the restriction is lifted — you can participate in as many transactions as you want. This fundamentally changes the strategy. Instead of hunting for the single best pair, you want to capture every profitable price movement in the array.

The Core Insight

Look at the price chart mentally. Every time the price goes up from one day to the next, that's money on the table. The question is — how do you collect all of it?

The answer is surprisingly simple: add every single upward price difference to your profit. If prices go up three days in a row from 1 → 3 → 5 → 8, you collect (3-1) + (5-3) + (8-5) = 7, which is exactly the same as buying at 1 and selling at 8. You never miss a gain.

This is the foundation of all approaches below.

Approach 1 — Simple Greedy (Collect Every Upward Move)

Intuition: Every time prices[i] > prices[i-1], add the difference to profit. You are essentially buying at every valley and selling at every peak, collecting each individual daily gain without explicitly tracking buy/sell days.

Why it works: The total gain from buying at day 0 and selling at day N is mathematically equal to the sum of all positive daily differences in between. You never lose anything by collecting gains day by day.

Example: prices = [1, 2, 3, 4, 5] Daily gains: (2-1) + (3-2) + (4-3) + (5-4) = 1+1+1+1 = 4 Same as buying at 1 and selling at 5 directly.

Time Complexity: O(N) — single pass through the array. Space Complexity: O(1) — no extra space used.

This is the cleanest and most recommended solution for this problem.

Approach 2 — Peak Valley Approach

Intuition: Instead of collecting every daily gain, explicitly find every valley (local minimum) to buy at and every peak (local maximum) to sell at. You buy when price stops falling and sell when price stops rising.

How it works: Scan through the array. When you find a valley (prices[i] ≤ prices[i+1]), that is your buy point. Then keep going until you find a peak (prices[i] ≥ prices[i+1]) — that is your sell point. Add the peak minus valley to profit. Repeat.

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

Valley at index 1 (price = 1), Peak at index 2 (price = 5) → profit += 4 Valley at index 3 (price = 3), Peak at index 4 (price = 6) → profit += 3 Total = 7 ✅

Time Complexity: O(N) — each element is visited at most twice. Space Complexity: O(1) — no extra space used.

This approach is more explicit and easier to visualize on a graph, though the code is slightly more involved than Approach 1.

Approach 3 — Two Pointer

Intuition: Use two pointers i (buy day) and j (sell day). Move j forward one step at a time. Whenever prices[j] > prices[i], you have a profitable window — add the profit and immediately move i to j (simulate selling and rebuying at the same price on the same day). Whenever prices[j] < prices[i], just move i to j since a cheaper buy day has been found.

Why moving i to j after every profitable sale works: Selling at j and immediately rebuying at j costs nothing (profit of 0 for that rebuy). But it positions i at the latest price so you can catch the next upward movement. This correctly simulates collecting every upward segment.

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

i=0, j=1 → 7 > 1, move i to 1. j=2. i=1, j=2 → 1 < 5, profit += 4, move i to 2. j=3. i=2, j=3 → 5 > 3, move i to 3. j=4. i=3, j=4 → 3 < 6, profit += 3, move i to 4. j=5. i=4, j=5 → 6 > 4, move i to 5. j=6. Loop ends. Total profit = 7 ✅

Time Complexity: O(N) — j traverses the array exactly once. Space Complexity: O(1) — only three integer variables.

This approach is functionally identical to Approach 1 — both collect every upward daily movement. The two pointer framing makes the buy/sell simulation more explicit.

Approach 4 — Dynamic Programming

Intuition: At any point in time, you are in one of two states — either you hold a stock or you do not hold a stock. Define two DP values updated each day:

1. hold = maximum profit if you are currently holding a stock at the end of this day.
2. cash = maximum profit if you are not holding any stock at the end of this day.

Transitions:

1. To hold on day i: either you already held yesterday, or you buy today. hold = max(hold, cash - prices[i])
2. To have cash on day i: either you already had cash yesterday, or you sell today. cash = max(cash, hold + prices[i])

Initialization:

1. hold = -prices[0] (you bought on day 0)
2. cash = 0 (you did nothing on day 0)

Time Complexity: O(N) — single pass. Space Complexity: O(1) — only two variables maintained at each step.

This approach is the most powerful because it extends naturally to harder variants of this problem — like LeetCode 309 (with cooldown) and LeetCode 714 (with transaction fee) — where greedy no longer works and you need explicit state tracking.

Dry Run — All Approaches on Example 1

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

Approach 1 (Simple Greedy): Day 1→2: 1 - 7 = -6, skip. Day 2→3: 5 - 1 = 4, add. profit = 4. Day 3→4: 3 - 5 = -2, skip. Day 4→5: 6 - 3 = 3, add. profit = 7. Day 5→6: 4 - 6 = -2, skip. Result = 7 ✅

Approach 4 (DP): Start: hold = -7, cash = 0. Day 1 (price=1): hold = max(-7, 0-1) = -1. cash = max(0, -1+1) = 0. Day 2 (price=5): hold = max(-1, 0-5) = -1. cash = max(0, -1+5) = 4. Day 3 (price=3): hold = max(-1, 4-3) = 1. cash = max(4, 1+3) = 4. Day 4 (price=6): hold = max(1, 4-6) = 1. cash = max(4, 1+6) = 7. Day 5 (price=4): hold = max(1, 7-4) = 3. cash = max(7, 3+4) = 7. Result = 7 ✅

Comparison of All Approaches

Approach 1 — Simple Greedy Code simplicity: Simplest possible. Best for interviews — clean and readable. Does not extend to constrained variants.

Approach 2 — Peak Valley Code simplicity: Moderate. Best for visual/conceptual understanding. Slightly verbose but maps directly to a chart.

Approach 3 — Two Pointer Code simplicity: Simple. Explicit simulation of buy/sell actions. Functionally identical to Approach 1.

Approach 4 — Dynamic Programming Code simplicity: Moderate. Most powerful — extends to cooldown, fee, and k-transaction variants. Worth mastering for the full stock problem series.

Common Mistakes to Avoid

Thinking you need to find exact buy/sell days: The problem only asks for maximum profit — you do not need to output which days you traded. This frees you to use the simple greedy sum approach.

Trying to find the global minimum and maximum: Unlike LeetCode 121, the single best buy-sell pair is not always optimal here. You need to capture multiple smaller movements, not one big one.

Holding more than one share: You cannot buy twice in a row without selling in between. In Approach 3, moving i = j after every transaction ensures you always sell before the next buy.

Not handling a flat or decreasing array: If prices never go up, all approaches correctly return 0 — the greedy sum adds nothing, peak-valley finds no valid pairs, and DP's cash stays at 0.

Complexity Summary

All four approaches run in O(N) time and O(1) space. The difference between them is conceptual clarity and extensibility, not raw performance.

The Full Stock Problem Series on LeetCode

This problem is part of a six-problem series. Understanding them in order builds intuition progressively:

LeetCode 121 — One transaction only. Two pointer / min tracking greedy. [ Blog is also avaliable on this - Read Now]

LeetCode 123 — At most 2 transactions. DP with explicit state for two transactions. [ Blog is also avaliable on this - Read Now]

LeetCode 188 — At most k transactions. Generalized DP.

LeetCode 309 — Unlimited transactions with cooldown after selling. DP with three states.

LeetCode 714 — Unlimited transactions with a fee per transaction. DP with adjusted transitions.

Each problem adds one constraint on top of the previous. If you understand the DP state machine from Approach 4 deeply, every problem in this series becomes a small modification of the same framework.

Key Takeaways

✅ When transactions are unlimited, collect every upward daily price movement — that is the global optimum.

✅ The sum of all positive daily differences equals the sum of all peak-valley differences. Both are provably optimal.

✅ The two pointer approach explicitly simulates buy and sell events — moving i = j after a sale means selling and immediately rebuying at the same price to stay positioned for the next gain.

✅ The DP approach with hold and cash states is the most versatile — it is the foundation for every harder variant in the stock series.

✅ Always initialize maxProfit = 0 so that the no-profit case (prices only falling) is handled correctly without extra conditions.

Happy Coding! Once you have this problem locked down, the rest of the stock series will feel like natural extensions rather than new problems entirely. 🚀