Best Time to Buy and Sell Stock II: Greedy Profit Collection

You are given an array prices where prices[i] is the price of a stock on day i. You can complete as many transactions as you like (buy one share, sell one share), but you must sell before buying again. Find the maximum profit.

This is LeetCode 122: Best Time to Buy and Sell Stock II, a medium problem that builds on the single-transaction version (LeetCode 121). The twist is that you can trade multiple times. That opens the door to a beautifully simple greedy strategy.

Why this problem matters

This problem is a textbook example of greedy profit collection. The core idea is that you do not need to figure out the optimal buy/sell pairs. You just need to collect every upward price movement. That single insight eliminates all the complexity of tracking transactions or optimizing over multiple intervals.

If you solved the single-transaction version by tracking a running minimum, you might expect this version to need something more complex. It does not. In fact, the greedy solution here is even simpler.

The brute force approach

You could try every combination of buy/sell pairs using recursion or dynamic programming. At each day, you decide whether to buy, sell, or hold. This leads to an exponential number of states if done naively, or O(n) states with memoization. But there is a much simpler way.

The key observation is that any multi-day profit can be decomposed into consecutive single-day gains. Consider prices [1, 2, 3, 4, 5]. Buying at 1 and selling at 5 gives a profit of 4. But that is exactly the same as:

• Day 1 to 2: 2 - 1 = 1
• Day 2 to 3: 3 - 2 = 1
• Day 3 to 4: 4 - 3 = 1
• Day 4 to 5: 5 - 4 = 1
• Total: 1 + 1 + 1 + 1 = 4

Every upward multi-day move equals the sum of its consecutive daily gains. This means you do not need to find optimal intervals at all. Just add up every positive day-over-day difference.

The greedy approach

The algorithm is: walk through the array starting at index 1. For each pair of consecutive days, if today's price is higher than yesterday's price, add the difference to your profit. Skip all downward moves.

That is the entire algorithm. If prices[i] is greater than prices[i-1], add prices[i] - prices[i-1] to your total profit.

Walking through it step by step

Let's trace through the example prices = [7, 1, 5, 3, 6, 4]. At each step, you compare the current price to the previous price. If the current price is higher, you add the difference to your running profit.

The answer is 7. You collected two upward moves: 5 - 1 = 4 and 6 - 3 = 3. The downward moves (7 to 1, 5 to 3, 6 to 4) contributed nothing.

This is equivalent to buying at 1, selling at 5, buying at 3, selling at 6. But the greedy approach never explicitly tracks buy/sell pairs. It just sums the gains.

The code

Here is the greedy solution in Python:

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

Four lines of logic. Here is what each piece does:

1. Start profit at 0. There is no profit before any comparison.
2. Loop from index 1 to the end. You need a previous element to compare against.
3. If the current price is higher than the previous price, add the difference to profit. This captures every upward move.
4. Return profit. If prices only went down, the answer is 0 because you never added anything.

Complexity analysis

Time: O(n). You visit each price exactly once. Each visit does O(1) work (one comparison and possibly one addition). Total: O(n).

Space: O(1). You use a single variable profit regardless of input size. No extra arrays, no hash maps, no stacks.

The greedy approach matches the optimal time and space while being far simpler to implement and reason about.

Why the greedy approach works

Not every problem can be solved greedily. Greedy works when locally optimal choices lead to a globally optimal solution. Here, that holds because:

• Any profitable multi-day hold can be decomposed into a sum of consecutive daily gains.
• Collecting every positive daily difference gives you the same total as the best possible sequence of buy/sell transactions.
• Skipping negative differences is always correct because holding through a price drop never helps.

There is no scenario where ignoring an upward move leads to a better outcome later. Each positive difference is independent and additive.

Building blocks

This problem is built on a single reusable pattern: greedy local profit collection.

The core idea is: when the optimal global solution equals the sum of locally optimal decisions, you can build the answer incrementally in one pass. At each position, you check whether a local gain exists and collect it if so. No backtracking, no future lookahead.

This same pattern appears in other problems:

• Gas Station (LeetCode 134): collect running fuel surplus, reset when it goes negative.
• Jump Game (LeetCode 55): greedily extend the farthest reachable index.
• Maximum Subarray (Kadane's): extend the current subarray or restart, collecting the best sum.

The skeleton is always the same: iterate once, accumulate gains, skip losses. The specifics of what counts as a "gain" and how you accumulate change from problem to problem, but the underlying pattern is identical. Once you internalize greedy local collection as a building block, these problems stop feeling like separate challenges.

Edge cases

Before submitting, make sure your solution handles these:

• Decreasing prices like [5, 4, 3, 2, 1]: no positive consecutive difference exists, return 0.
• Always increasing like [1, 2, 3, 4, 5]: every consecutive pair contributes. Profit = 4, same as buying on day 0 and selling on day 4.
• Single day [5]: the loop body never executes (range starts at 1, which is past the end). Return 0.
• Two days [1, 5]: one comparison. 5 > 1, so profit = 4. [5, 1]: 1 is not greater than 5, profit = 0.

The greedy solution handles all of these without special-case logic.

From understanding to recall

You have read through the greedy solution and it makes sense. Collect every positive difference, ignore every negative one. Simple. But can you write it from scratch in an interview without looking at it?

The details matter: starting the loop at index 1, comparing prices[i] to prices[i-1], only adding when the difference is positive. These are small but easy to second-guess under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the greedy collection loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "multiple transactions allowed, maximize profit" and the code flows out without hesitation.

Greedy local profit collection is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Best Time to Buy and Sell Stock - The single-transaction version that uses running minimum instead of greedy collection
• Gas Station - Another greedy problem where collecting running surplus in one pass gives the optimal answer

CodeBricks breaks the buy and sell stock II problem into its greedy local collection building block, then drills it independently with spaced repetition. You type the pattern from scratch until it is automatic. When a greedy problem shows up in your interview, you do not think about it. You just write it.