LeetCode 122 - Best Time to Buy and Sell Stock II

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Greedy

Solution

Problem Understanding

This problem asks us to maximize profit from stock trading over a sequence of days. We are given an array prices, where prices[i] represents the stock price on the ith day. We are allowed to perform as many buy and sell transactions as we want, with one important restriction: at any moment, we can hold at most one share of stock.

Unlike the original "Best Time to Buy and Sell Stock" problem, where only one transaction is allowed, here we can repeatedly buy and sell. Additionally, the problem explicitly states that selling and buying on the same day is allowed, as long as we never hold more than one share at a time. This detail matters because it means we can chain profitable opportunities together without restriction.

The goal is to compute the maximum total profit achievable. If the stock price only decreases, then the best decision is to make no trades, resulting in a profit of 0.

The constraints provide useful hints about expected efficiency:

1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4

The input size can grow up to 30,000 elements, which rules out exponential or quadratic approaches in practice. We should aim for a linear time solution, ideally O(n).

Several edge cases are important to recognize upfront. If the array contains only one day, no transaction can occur because buying and selling require at least two days. If prices are strictly decreasing, the answer should be 0 since every trade would lose money. If prices are strictly increasing, the optimal strategy is effectively to buy once at the beginning and sell at the end, though the algorithm may conceptually perform smaller intermediate trades. Repeated equal prices also need careful handling, since buying and selling at the same value provides no gain.

Approaches

Brute Force Approach

A brute force strategy would attempt to explore every possible sequence of buy and sell decisions. At each day, we could choose whether to buy, sell, or do nothing, while respecting the constraint that only one stock can be held at a time.

This can be formulated as a recursive search or dynamic programming exploration where we consider every possible transaction combination. For example, after buying on one day, we could try selling on every future day and recursively solve the remaining problem.

The brute force method guarantees correctness because it exhaustively considers every valid trading sequence and chooses the one with maximum profit. However, its runtime grows exponentially since every day introduces branching decisions. With up to 30,000 days, this becomes computationally infeasible.

Optimal Greedy Approach

The key observation is that every profitable upward movement can be safely captured independently.

Suppose the stock price goes from 1 → 2 → 3 → 4. We could buy at 1 and sell at 4, earning 3. Alternatively:

Buy at 1, sell at 2, profit 1
Buy at 2, sell at 3, profit 1
Buy at 3, sell at 4, profit 1

The total is still 3.

This insight means we do not need to search for perfect valleys and peaks explicitly. Instead, whenever today's price is higher than yesterday's, we simply add the difference to our profit. We effectively collect every positive gain.

This works because any long profitable interval can be decomposed into smaller profitable daily increases without changing the total profit.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Tries all buy/sell decision combinations recursively
Optimal Greedy	O(n)	O(1)	Adds every positive day-to-day price increase

Algorithm Walkthrough

Initialize a variable called total_profit to 0.

This variable will store the cumulative profit earned from all successful transactions. 2. Iterate through the array starting from the second day.

We compare each day's price with the previous day's price because profit opportunities arise only when the price increases. 3. Check whether today's price is greater than yesterday's price.

If prices[i] > prices[i - 1], then there is profit to be made from this upward movement. 4. Add the positive difference to total_profit.

Specifically, add:

prices[i] - prices[i - 1]

This represents buying yesterday and selling today, or equivalently capturing that segment of profit. 5. Ignore non-profitable movements.

If today's price is equal to or lower than yesterday's, we skip it because trading would not increase profit. 6. Continue until the end of the array.

After processing all days, total_profit contains the maximum achievable profit.

Why it works

The algorithm works because any profitable sequence of increasing prices can be decomposed into individual daily gains. For an increasing segment:

buy at a, sell at d
profit = d - a

This is mathematically equivalent to:

(b - a) + (c - b) + (d - c) = d - a

By summing all positive daily differences, we capture exactly the same profit as an optimal sequence of buys and sells. Since no additional profit can be extracted from declining intervals, skipping them is always optimal.

Python Solution

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        total_profit = 0

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

        return total_profit

The implementation begins by initializing total_profit to zero. This variable accumulates all profitable gains found during iteration.

The loop starts from index 1 because each day's price must be compared with the previous day. For every position, we check whether the current day's price exceeds the previous day's price. If it does, we add the difference to the running profit.

Declining or unchanged prices are ignored because they cannot contribute positive profit. Once the loop finishes, the accumulated value is returned as the maximum possible profit.

The implementation directly mirrors the greedy reasoning described earlier. Instead of explicitly simulating buy and sell operations, it captures the profit of every increasing price segment.

Go Solution

func maxProfit(prices []int) int {
    totalProfit := 0

    for i := 1; i < len(prices); i++ {
        if prices[i] > prices[i-1] {
            totalProfit += prices[i] - prices[i-1]
        }
    }

    return totalProfit
}

The Go implementation follows the same logic as the Python version. We iterate through the slice starting at index 1, compare adjacent prices, and accumulate positive differences.

There are no special concerns around nil versus empty slices because the problem guarantees at least one element. Integer overflow is also not an issue since the maximum possible profit remains comfortably within Go's int range under the given constraints.

Worked Examples

Example 1

Input:

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

Day	Price	Previous Price	Difference	Profit Added	Total Profit
0	7	-	-	0	0
1	1	7	-6	0	0
2	5	1	+4	4	4
3	3	5	-2	0	4
4	6	3	+3	3	7
5	4	6	-2	0	7

Final answer:

The algorithm captures the two profitable segments: 1 → 5 and 3 → 6.

Example 2

Input:

prices = [1,2,3,4,5]

Day	Price	Previous Price	Difference	Profit Added	Total Profit
0	1	-	-	0	0
1	2	1	+1	1	1
2	3	2	+1	1	2
3	4	3	+1	1	3
4	5	4	+1	1	4

Final answer:

Although we conceptually collect daily profits, the total equals buying at 1 and selling at 5.

Example 3

Input:

prices = [7,6,4,3,1]

Day	Price	Previous Price	Difference
0	7	-	-
1	6	7	-1
2	4	6	-2
3	3	4	-1
4	1	3	-2

Final answer:

Since prices always decrease, no profitable trade exists.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the array once, processing each day exactly once
Space	O(1)	Only a few variables are used regardless of input size

The algorithm performs a single pass through the input array, making the runtime linear with respect to the number of days. Memory usage remains constant because we only maintain a running profit total and loop index, without allocating extra data structures.

Test Cases

solution = Solution()

assert solution.maxProfit([7, 1, 5, 3, 6, 4]) == 7  # Example 1, multiple profitable trades
assert solution.maxProfit([1, 2, 3, 4, 5]) == 4  # Example 2, continuously increasing
assert solution.maxProfit([7, 6, 4, 3, 1]) == 0  # Example 3, continuously decreasing

assert solution.maxProfit([5]) == 0  # Single day, no trade possible
assert solution.maxProfit([2, 2, 2, 2]) == 0  # Constant prices, no profit
assert solution.maxProfit([1, 5]) == 4  # Simple profitable trade
assert solution.maxProfit([5, 1]) == 0  # No profitable trade
assert solution.maxProfit([1, 3, 2, 5, 4, 7]) == 8  # Multiple buy/sell opportunities
assert solution.maxProfit([0, 10000]) == 10000  # Boundary stock values
assert solution.maxProfit([3, 2, 6, 5, 0, 3]) == 7  # Mixed increases and decreases

Test	Why
`[7,1,5,3,6,4]`	Validates multiple profitable transactions
`[1,2,3,4,5]`	Confirms increasing sequence handling
`[7,6,4,3,1]`	Ensures decreasing prices return `0`
`[5]`	Tests smallest valid input
`[2,2,2,2]`	Verifies equal prices do not create profit
`[1,5]`	Simple single profitable transaction
`[5,1]`	Simple non-profitable case
`[1,3,2,5,4,7]`	Tests multiple alternating opportunities
`[0,10000]`	Validates boundary values
`[3,2,6,5,0,3]`	Checks mixed market movements

Edge Cases

A single-day input is an important boundary case. Since profit requires both a buy and a sell operation, one day alone cannot produce any transaction. A naive implementation that assumes at least two elements could trigger an out-of-bounds access. This implementation handles it naturally because the loop starts at index 1, meaning no iteration occurs and 0 is returned.

A strictly decreasing price sequence can also cause bugs in incorrect solutions. Some implementations mistakenly force at least one transaction or attempt to track peaks and valleys incorrectly. For an input such as [7,6,4,3,1], every daily difference is negative, so the algorithm simply skips all days and returns 0.

Repeated equal prices deserve special attention because buying and selling at the same price produces no gain. For example, [2,2,2,2] should return 0. Since the implementation only adds profit when prices[i] > prices[i - 1], equal values are ignored automatically.

A sequence with alternating rises and drops is another subtle case. For example, [1,3,2,5,4,7] requires multiple independent transactions to maximize profit. A naive strategy that only buys once and sells once would miss profit opportunities. By summing every positive increase, the implementation correctly captures all available gains.