122. Best Time to Buy and Sell Stock II (Medium)

Problem

You are given an integer array prices where prices[i] is the price of a stock on day i. Each day you may buy and/or sell, but you can hold at most one share at any time. You may complete as many transactions as you like. Return the maximum profit.

Unlike 121. Best Time to Buy and Sell Stock, which allows only a single buy-sell pair, this version allows unlimited transactions. That one change flips the problem from “find the single best window” to “collect every gain you can.”

Examples

[7,1,5,3,6,4] → 7: buy at 1 sell at 5 (+4), buy at 3 sell at 6 (+3).
[1,2,3,4,5] → 4: buy at 1, sell at 5. One climb, no dips.
[7,6,4,3,1] → 0: prices only fall, so never buy.

Constraints

$1 \leq \text{prices.length} \leq 3 \times 10^4$
$0 \leq \text{prices}[i] \leq 10^4$

LeetCode 122 · Link · Medium

Try it yourself

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Peak and valley

The intuitive picture: profit comes from buying at a valley (local minimum) and selling at the next peak (local maximum). Walk the array, slide down to each valley, slide up to the following peak, and bank peak − valley. Repeat to the end.

def maxProfit(prices: list[int]) -> int:
    n = len(prices)
    i = 0
    profit = 0
    while i < n - 1:                                         # L1: scan the array
        while i < n - 1 and prices[i + 1] <= prices[i]:     # L2: descend to a valley
            i += 1
        valley = prices[i]
        while i < n - 1 and prices[i + 1] >= prices[i]:     # L3: climb to a peak
            i += 1
        profit += prices[i] - valley                        # L4: bank the rise
    return profit

function maxProfit(prices: number[]): number {
    const n = prices.length;
    let i = 0;
    let profit = 0;
    while (i < n - 1) {                                      // L1: scan the array
        while (i < n - 1 && prices[i + 1] <= prices[i]) i++; // L2: descend to a valley
        const valley = prices[i];
        while (i < n - 1 && prices[i + 1] >= prices[i]) i++; // L3: climb to a peak
        profit += prices[i] - valley;                        // L4: bank the rise
    }
    return profit;
}

func maxProfit(prices []int) int {
    n := len(prices)
    i := 0
    profit := 0
    for i < n-1 {                                           // L1: scan the array
        for i < n-1 && prices[i+1] <= prices[i] {           // L2: descend to a valley
            i++
        }
        valley := prices[i]
        for i < n-1 && prices[i+1] >= prices[i] {           // L3: climb to a peak
            i++
        }
        profit += prices[i] - valley                        // L4: bank the rise
    }
    return profit
}

final class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var index = 0, profit = 0
        while index < prices.count - 1 {
            while index < prices.count - 1 && prices[index] >= prices[index + 1] { index += 1 }
            let valley = prices[index]
            while index < prices.count - 1 && prices[index] <= prices[index + 1] { index += 1 }
            profit += prices[index] - valley
        }
        return profit
    }
}

Where the time goes, line by line

Variables: n = len(prices).

Line	Per-call cost	Times executed	Contribution
L2 descend	$O(1)$	$n$ total across all valleys	$O(n)$
L3 climb	$O(1)$	$n$ total across all peaks	$O(n)$
L4 bank	$O(1)$	peaks visited	$O(n)$

Complexity

Time: $O(n)$ , each index advanced once.
Space: $O(1)$ .

Approach 2: Greedy, sum every climb

Peak-and-valley is correct but fiddly. Here is the collapse: a rise from valley to peak equals the sum of every up-step in between. So you do not need to find peaks and valleys at all. Just add up every positive day-to-day difference.

prices = [1, 5, 3, 6]

valley-to-peak view:  (5-1) + (6-3) = 4 + 3 = 7
day-to-day view:      (5-1) + (6-3) = 4 + 3 = 7   ← skip the 5→3 drop

If the price rises today, pretend you bought yesterday and sell today. Down-days contribute nothing because you simply hold no share.

def maxProfit(prices: list[int]) -> int:
    profit = 0
    for i in range(1, len(prices)):                         # L1: scan adjacent pairs
        if prices[i] > prices[i - 1]:                       # L2: only count up-days
            profit += prices[i] - prices[i - 1]             # L3: bank the daily gain
    return profit

function maxProfit(prices: number[]): number {
    let profit = 0;
    for (let i = 1; i < prices.length; i++) {               // L1: scan adjacent pairs
        if (prices[i] > prices[i - 1])                      // L2: only count up-days
            profit += prices[i] - prices[i - 1];            // L3: bank the daily gain
    }
    return profit;
}

func maxProfit(prices []int) int {
    profit := 0
    for i := 1; i < len(prices); i++ {                      // L1: scan adjacent pairs
        if prices[i] > prices[i-1] {                        // L2: only count up-days
            profit += prices[i] - prices[i-1]               // L3: bank the daily gain
        }
    }
    return profit
}

final class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        zip(prices, prices.dropFirst()).reduce(0) { $0 + max(0, $1.1 - $1.0) }
    }
}

Why summing up-steps is optimal

A telescoping argument. Any profitable holding period from day b to day s has value prices[s] − prices[b], which equals the sum of the consecutive differences (prices[b+1] − prices[b]) + ... + (prices[s] − prices[s-1]). The negative differences inside that span only shrink the total, so dropping them (by not holding on down-days) can never lose money, and capturing every positive difference can never be beaten. Because you may transact freely, you are allowed to take exactly the positive steps and skip the rest.

Where the time goes, line by line

Variables: n = len(prices).

Line	Per-call cost	Times executed	Contribution
L1 loop	$O(1)$	$n - 1$	$O(n)$
L3 bank gain	$O(1)$	up to $n - 1$	$O(n)$

Complexity

Time: $O(n)$ , one pass.
Space: $O(1)$ .

Approach 3: State machine (hold vs cash)

The most general framing, the one that scales to the harder variants (cooldown, fees, capped transaction count). Track two running bests:

cash: most profit you can have holding no share right now.
hold: most profit you can have holding one share right now (a negative number early on, since buying costs money).

Each day, either act or do nothing, and keep the better of the two.

def maxProfit(prices: list[int]) -> int:
    cash = 0                                                # L1: no share held
    hold = float('-inf')                                    # L2: one share held
    for p in prices:                                        # L3: each day
        cash = max(cash, hold + p)                          # L4: sell or stay flat
        hold = max(hold, cash - p)                          # L5: buy or keep holding
    return cash

function maxProfit(prices: number[]): number {
    let cash = 0;                                           // L1: no share held
    let hold = -Infinity;                                   // L2: one share held
    for (const p of prices) {                               // L3: each day
        cash = Math.max(cash, hold + p);                    // L4: sell or stay flat
        hold = Math.max(hold, cash - p);                    // L5: buy or keep holding
    }
    return cash;
}

func maxProfit(prices []int) int {
    cash := 0                                               // L1: no share held
    hold := math.MinInt32                                   // L2: one share held
    for _, p := range prices {                              // L3: each day
        cash = max(cash, hold+p)                            // L4: sell or stay flat
        hold = max(hold, cash-p)                            // L5: buy or keep holding
    }
    return cash
}

final class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var cash = 0, hold = -prices[0]
        for price in prices.dropFirst() {
            let previousCash = cash
            cash = max(cash, hold + price)
            hold = max(hold, previousCash - price)
        }
        return cash
    }
}

This is identical in result to Approach 2 but expresses the decision explicitly, which is why it generalizes. Returning cash (not hold) is correct because you never want to finish the day still holding a share, an unsold share is unrealized profit worth nothing at the close.

Complexity

Time: $O(n)$ , one pass.
Space: $O(1)$ , two scalars.

How to recognize this pattern

The signal: “as many transactions as you like” plus “at most one share.” That pairing is the tell. Unlimited transactions with no cooldown and no fee means there is nothing stopping you from capturing every single up-day. The moment a constraint removes friction like that, ask whether the answer is just “sum all the gains.”

The contrast that defines it. Compare the three stock problems:

Problem	Constraint	Optimal idea
121. Buy and Sell Stock	one transaction	Track min price so far, max single window
122. Buy and Sell Stock II	unlimited transactions	Sum every positive day-to-day difference
309. With Cooldown	unlimited, but 1-day rest after selling	State machine, the friction breaks the greedy sum

The single-transaction version (121) is a sliding-window/running-minimum problem. Add unlimited transactions and it collapses to the trivial greedy sum (122). Add a cooldown or a fee and the greedy sum breaks, friction forces you back to the state machine (Approach 3). Recognizing which friction is present tells you which tool to reach for.

The wrong first move: overthinking it as DP. Many people see “maximize profit over a sequence of decisions” and immediately reach for a 2D DP table over (day, holding-state). That works, but for this specific problem it is a sledgehammer. The greedy one-liner is correct and provably optimal because there is no friction. Save the DP for when a constraint actually couples your decisions across days.

The mental model. With no transaction limit, every up-day is independent free money. You are not choosing when to be in the market, you are choosing to ride every uphill and sit out every downhill. There is no opportunity cost to selling and re-buying because both can happen the same day.

Problem	Same shape
53. Maximum Subarray	Accumulate local gains, drop what hurts the running total
1710. Maximum Units on a Truck	Greedily take the best available unit each step
605. Can Place Flowers	Take every locally-valid opportunity, no lookahead needed

What a transaction fee breaks (and why)

The greedy sum works because, with no friction, splitting one climb into daily steps is free. Buy-and-sell every up-day, or buy once and hold through the whole climb, both capture the same total. Add a per-sale fee and that equivalence collapses, because every split now costs another fee.

Watch it break on a tiny case. Prices [1, 2, 3] with a $1 fee per sale:

day-to-day steps:  +1, +1

decompose into daily trades (the greedy view):
  buy 1 / sell 2  →  +1 gross − $1 fee = 0
  buy 2 / sell 3  →  +1 gross − $1 fee = 0
  total: $0        ← two trades, two fees, both wiped out

merge into one hold:
  buy 1 / sell 3  →  +2 gross − $1 fee = $1
  total: $1        ← one trade, one fee

Same $2 gross climb, but the daily-step view pays the toll twice and nets nothing, while one long hold pays it once and nets a dollar. Summing positive daily steps and subtracting a fee per step gives the wrong answer here: it returns 0 when the real maximum is 1.

The lesson cuts both ways:

No friction → every up-day is independent → sum the positive steps. Splitting is free, so it never hurts.
Any friction (a fee, a cooldown) → days are coupled → you can no longer decompose into daily steps. Now you want the opposite move: merge consecutive up-days into one hold and pay the fee once. Whether to act today depends on whether you are already holding, which is exactly the state the day-to-day trick throws away.

That coupling is why the friction variants need the hold/cash state machine (Approach 3), not the greedy sum. The state machine carries “am I holding a share right now?” across days, so it can decide to ride through a dip rather than sell into it. 714. Best Time to Buy and Sell Stock with Transaction Fee subtracts the fee inside the cash = max(cash, hold + p - fee) step; 309. Best Time to Buy and Sell Stock with Cooldown adds a third “resting” state. Same skeleton, one extra rule each.

Key takeaways

Unlimited transactions with no friction means: sum every positive prices[i] − prices[i-1]. That is the whole solution.
A valley-to-peak rise equals the sum of the up-steps inside it, so peak-finding is unnecessary, the daily-difference sum captures the same profit.
Down-days contribute nothing because you simply hold no share through them.
The hold/cash state machine gives the same answer and is the version to remember, it survives when cooldowns or fees break the greedy sum.
A per-sale fee couples your days: splitting one climb into daily trades now pays the fee on every step, so you merge consecutive up-days into a single hold and pay once. Summing daily steps minus a per-step fee is wrong (it returns 0 on [1,2,3] with a $1 fee when the answer is 1).
Contrast with 121 (single transaction, running-min window): the constraint, not the surface, picks the technique.

Greedy Algorithms, the local choice pattern protected by an invariant about the best reachable future.
Array Scans, the linear pass habit of carrying just enough state while reading each item once.

122. Best Time to Buy and Sell Stock II (Medium)

Problem

Try it yourself

Approach 1: Peak and valley

Approach 2: Greedy, sum every climb

Approach 3: State machine (hold vs cash)

How to recognize this pattern

What a transaction fee breaks (and why)

Key takeaways

Related topics

Related concepts