Generated by Codex with GPT-5
Difficulty: MEDIUM
Problem: Best Time to Buy and Sell Stock II
Problem gist
The input is a list of stock prices where prices[i] is the price on day i. The goal is to make as much profit as possible by buying and selling any number of times.
There are two important rules:
You may complete many transactions, but you can hold at most one share at a time. That means a new buy must happen after the previous sell.
A buy and sell can happen on the same day in the abstract model, but doing so never creates profit. The useful transactions are the ones that capture upward price movement.
Optimal idea
The optimal greedy solution is to add every positive day-to-day price increase.
If today’s price is higher than yesterday’s price, owning the stock across that one-day step earns exactly prices[i] - prices[i - 1]. If today’s price is lower or equal, owning across that step does not help, so it should be skipped.
This works because any longer profitable transaction can be split into the same set of one-day gains. For example, buying at 1 and selling at 5 earns 4. If the price path was 1 -> 2 -> 3 -> 5, the one-day gains are 1 + 1 + 2 = 4, exactly the same profit. Splitting the transaction does not change the total, and the problem allows multiple transactions.
So the best strategy is not to predict the absolute lowest buy day or highest sell day. It is to capture every upward edge in the price chart.
How to derive the solution
Start with the simplest profitable pattern: if the price rises from one day to the next, buying before the rise and selling after it makes money. If the price falls, that step should not be part of any profitable holding period.
Now look at a longer rising run, such as:
1, 3, 4, 8
Buying at 1 and selling at 8 gives profit 7. Adding each positive adjacent difference also gives (3 - 1) + (4 - 3) + (8 - 4) = 7. The two views are equivalent.
For a mixed run, such as:
1, 5, 3, 6
The falling step from 5 to 3 should be avoided. The best profit is (5 - 1) + (6 - 3) = 7, which is exactly the sum of positive adjacent gains.
This gives a local rule that is globally optimal: scan left to right, and whenever prices[i] > prices[i - 1], add that difference to the answer.
Python solution
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
return self._profit_from_all_upward_moves(prices)
def _profit_from_all_upward_moves(self, prices: List[int]) -> int:
total_profit = 0
for day in range(1, len(prices)):
previous_price = prices[day - 1]
current_price = prices[day]
# Holding the stock across this step is useful only when the
# price rises. Every such rise can be captured independently.
if current_price > previous_price:
total_profit += current_price - previous_price
return total_profitThe time complexity is O(n) because the solution scans the price list once. The space complexity is O(1) because it stores only the running profit.
Interview follow-ups
What if only one transaction is allowed?
The greedy “sum every increase” approach no longer works because multiple rising segments cannot all be captured. The solution becomes tracking the lowest price seen so far and the best profit from selling today.
As the scan moves left to right, keep lowest_buy_price = min(lowest_buy_price, current_price). The best sell profit for the current day is current_price - lowest_buy_price. Updating the maximum over all days gives the answer.
This works because the buy day must come before the sell day, and the cheapest earlier price is always the best partner for a sale on the current day. The complexity stays O(n) time and O(1) space.
What if at most two transactions are allowed?
Use dynamic programming with transaction states. Track the best balance after the first buy, first sell, second buy, and second sell. Each state represents the best profit possible after performing that action by the current day.
For each price, update the states in order: first buy may spend money, first sell may realize profit, second buy may spend from the first profit, and second sell may realize the final answer. This compresses the DP table into four variables.
The reason it works is that every valid sequence of up to two transactions must pass through those states in order. The running state values keep the best possible outcome for each stage. The complexity is O(n) time and O(1) space.
What if at most k transactions are allowed?
Use dynamic programming where buy[t] is the best balance after the tth buy and sell[t] is the best profit after the tth sell. For each price, update every transaction count from 1 through k.
The recurrence is buy[t] = max(buy[t], sell[t - 1] - price) and sell[t] = max(sell[t], buy[t] + price). The final answer is sell[k].
This runs in O(nk) time and O(k) space. There is also an important shortcut: if k >= n / 2, the transaction limit is effectively unlimited, so the original greedy solution applies in O(n) time.
What if a cooldown day is required after selling?
The unlimited-transaction greedy solution breaks because selling today can block buying tomorrow. The usual solution is dynamic programming with three states: holding a stock, sold today, and resting.
On each day, hold can come from continuing to hold or buying from a previous rest state. sold comes from selling a previously held stock. rest comes from doing nothing after either resting or having sold earlier.
This works because the cooldown rule depends on the previous day’s state, not on the full transaction history. The complexity is O(n) time and O(1) space after compressing the states.
What if every sale has a transaction fee?
The greedy adjacent-difference rule is no longer enough because small gains can be erased by repeated fees. Use two DP states: hold, the best profit while currently holding one share, and cash, the best profit while holding no share.
For each price, either keep holding or buy from cash; either keep cash or sell from hold and subtract the fee. The update is based on choosing the better of taking an action today or doing nothing.
This stays O(n) time and O(1) space. The tradeoff compared with the original problem is that the solution must decide when gains are large enough to justify paying the fee.
What if the interviewer asks for the actual buy and sell days?
Scan for rising runs. When a rise starts, mark the buy day at the local valley. Continue while prices keep rising, and sell at the local peak before the next drop. Repeat until the end.
This produces a compact list of transactions whose total profit matches the greedy sum of positive adjacent differences. It works because every maximal rising run can be represented as one buy at the start and one sell at the end without changing profit.
The complexity is still O(n) time. The extra space is O(m), where m is the number of returned transactions.