LeetCode 122 – Best Time to Buy and Sell Stock II

The sequel to Best Time to Buy and Sell Stock, and one of the rare cases where removing a constraint makes the problem easier. Unlimited transactions turn a scanning problem into a three-line greedy — and the greedy looks like cheating until you can say precisely why it is not.

The problem

You may buy and sell as many times as you like, but you can hold at most one share at a time — you must sell before buying again. Return the maximum profit.

[7,1,5,3,6,4]  -> 7      buy 1 sell 5 (+4), buy 3 sell 6 (+3)
[1,2,3,4,5]    -> 4      buy 1 sell 5 -- or buy and sell every day, same total
[7,6,4,3,1]    -> 0      never buy; profit cannot be negative
[1]            -> 0
[]             -> 0

Example 2 is the one that reveals the trick. Holding from day 1 to day 5 earns 4, and so does selling and rebuying every single day. Those are the same number, and that is not a coincidence.

Every rise is capturable, and nothing else is

A hold across several days earns exactly the sum of that stretch's day-to-day changes — the intermediate prices cancel:

buy at p[i], sell at p[j]
= p[j] - p[i]
= (p[i+1] - p[i]) + (p[i+2] - p[i+1]) + ... + (p[j] - p[j-1])

So every profit is a sum of consecutive daily deltas. With unlimited transactions you are free to choose any set of them, so you take every positive one and skip every negative one. No strategy can beat that, because no strategy can earn a delta that does not exist, and none is forced to accept a fall.

[7, 1, 5, 3, 6, 4]
 deltas: -6  +4  -2  +3  -2
 keep:       +4      +3     -> 7

That derivation is the answer. Without it the solution looks like it is trading on days it should not be; with it, it is obviously optimal.

Java

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;

        for (int i = 1; i < prices.length; i++) {
            // Every gain is a sum of daily deltas, so take each positive one.
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }

        return profit;
    }
}

The loop starts at 1 and never indexes out of range, so empty and single-element arrays return 0 without a guard. A falling market returns 0 because no delta is positive — profit is never negative, which the problem intends and the code enforces for free.

You may be asked whether this "really" buys and sells daily. It does not need to: the daily decomposition is a calculation, and the actual trades are the maximal rising runs. Both produce the same number, which is what the algebra above shows.

Python

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        return sum(max(today - yesterday, 0)
                   for yesterday, today in zip(prices, prices[1:]))

zip(prices, prices[1:]) is the idiomatic way to walk consecutive pairs, and it handles the short inputs on its own — an empty or single-element list produces no pairs, so the sum is 0.

Write the explicit loop first if the one-liner would hide your reasoning. A comprehension that arrives without explanation reads as recalled; the same line after the delta argument reads as derived.

The state-machine version, which is the one that generalises

The greedy is optimal here and stops working the moment a constraint returns — a transaction limit, a fee, a cooldown. The formulation that survives all of those tracks two states:

        int cash = 0;                 // best profit while holding NO share
        int hold = -prices[0];        // best profit while holding one share

        for (int i = 1; i < prices.length; i++) {
            int previousCash = cash;                          // yesterday's value
            cash = Math.max(cash, hold + prices[i]);          // sell today, or do nothing
            hold = Math.max(hold, previousCash - prices[i]);  // buy today, or keep holding
        }

        return cash;

The temporary matters. hold must be computed from yesterday's cash, not the value just written — using the fresh one lets the same day be both a sale and a purchase. It happens to be harmless with unlimited transactions, since a same-day round trip earns zero, but it is a real bug the instant a transaction fee or a limit is added.

Adding a fee is then cash = max(cash, hold + prices[i] - fee) (problem 714). A cooldown adds a third state (309). A cap of k transactions makes both states arrays indexed by transaction count (188). Mentioning that the greedy is a special case of this, rather than a separate idea, is the strongest thing you can say about the problem.

Complexity

One pass either way. Every price must be read, so there is no sub-linear answer.

The family

Six problems, one framework, and only two of them have a greedy shortcut. Knowing the table is worth more than knowing any single row.

What the interviewer is checking

• That you derive the delta decomposition rather than asserting the greedy.
• That you can explain why buying and selling daily is not cheating.
• A falling market returning 0, and empty or single-element input.
• That you know the greedy breaks under a fee, a cooldown or a transaction cap.
• The two-state formulation, and the temporary that keeps the days separate.
• That you connect it back to problem 121 rather than treating it as new.