Best Time to Buy and Sell Stock

Learning goal: Recognize the exact decision the stock problem asks us to optimize.

Core idea A valid transaction has a strict time order: the buying day must come before the selling day. For each possible selling day, we want the lowest price available among all earlier days. The answer is the best positive difference, while a sequence with no profitable transaction returns zero.

Algorithm plan

• Scan the prices from left to right.
• Treat the current day as a possible selling day.
• Remember the cheapest price seen before or on the current scan.
• Compare today's price with that minimum and update the best profit.

Micro-example For [7,1,5,3,6,4], buying at 1 and selling at 6 gives 6 - 1 = 5. The later sale is legal because the price 1 appears earlier in the array.

Pitfalls

• Buying and selling on the same day does not create a positive profit.
• A sale before the cheapest buy is invalid; the scan order prevents this.
• Negative gains should not replace the initial answer of zero.

Recap

• The transaction must move forward in time.
• Every sale needs the cheapest earlier buy.
• We can optimize all possible sales during one scan.

Learning goal: Understand why one running minimum summarizes every possible buy.

Core idea When we stand on a particular day, the only information needed about earlier prices is their minimum. Any more expensive earlier buy would produce less profit if sold today. Therefore, minPrice represents the best buy opportunity seen so far, and bestProfit records the strongest sale considered so far.

Algorithm plan

• Initialize minPrice to the first price.
• For each price, update minPrice if today's value is cheaper.
• Otherwise compute price - minPrice as today's candidate profit.
• Keep the larger of the candidate and bestProfit.

Micro-example After reading 7, the minimum is 7 and profit is 0. After reading 1, the minimum becomes 1; after reading 6, the candidate profit is 6 - 1 = 5.

Pitfalls

• Do not reset the minimum after finding a profit; a later sale may use it.
• Do not compare today's price with a future price.
• Updating the minimum and evaluating profit must respect the same-day rule.

Recap

• minPrice compresses all earlier buy choices.
• Each day contributes one possible sale.
• bestProfit is the maximum candidate seen so far.

Learning goal: Translate the running-minimum idea into a precise linear-time procedure.

Core idea View the scan as a moving window: the right edge is today's possible selling day, while the left side summarizes the best buy seen before it. When a new lower price appears, move the effective buy position to that day. Otherwise, evaluate the profit from the current buy to today's sale.

Algorithm plan

1. Set minPrice to a very large value and bestProfit to 0.
2. For each price in prices, replace minPrice when price is smaller.
3. Compute price - minPrice and maximize bestProfit.
4. Return bestProfit after the scan.

min_price = float("inf")
best_profit = 0
for price in prices:
    min_price = min(min_price, price)
    best_profit = max(best_profit, price - min_price)
return best_profit

Micro-example At price 5, the running minimum is 1, so the candidate is 4. At price 6, the candidate becomes 5, which replaces the previous best.

Pitfalls

• Initialize profit to zero so all-decreasing prices are handled.
• The minimum must be updated before evaluating the current day, making same-day profit zero.
• The scan stores values, not all pairs of indices.

Recap

• The moving right edge considers each sale once.
• The left-side summary is minPrice.
• The algorithm uses constant extra space.

Learning goal: Trace how minPrice and bestProfit evolve on a complete example.

Core idea Each price is processed exactly once as a possible sale. The current minimum may change when the price drops, but the best profit changes only when today's sale improves the answer. This makes the final result easy to audit: every day has contributed one candidate.

Algorithm plan

• Start with no known buy: minPrice = infinity, bestProfit = 0.
• Read 7: it becomes the minimum; profit remains zero.
• Read 1: replace the minimum because it is cheaper.
• Read 5, 3, 6, and 4: compare each against the best buy so far.
• Finish with bestProfit = 5.

Micro-example The decisive step is price 6: the minimum before it is 1, so the candidate is 6 - 1 = 5. Price 4 arrives later, but 4 - 1 = 3, so the answer stays 5.

Pitfalls

• A lower price updates the buy summary but does not create a negative answer.
• A later smaller price cannot erase a profit already found.
• Keep the original index order; sorting would destroy the time constraint.

Recap

• The trace has one state update per day.
• The best transaction is buy at index 1, sell at index 4.
• The returned profit is 5.

Learning goal: Identify the implementation mistake that turns this easy solution into a quadratic algorithm.

Core idea The tempting approach is to try every pair of days and calculate each profit. That works logically, but it repeats the same comparisons and takes O(n²) time. The running minimum avoids this repetition by preserving exactly the earlier information needed for today's sale.

Algorithm plan

• For an empty-profit situation, initialize bestProfit to 0.
• When prices decrease, update only minPrice.
• When prices increase, evaluate the difference and update bestProfit if needed.
• Never sort the array, because chronological order determines whether a transaction is legal.

Micro-example For [7,6,4,3,1], every candidate profit is negative or zero. The algorithm keeps bestProfit = 0, meaning no trade is preferable.

Pitfalls

• Do not return a negative profit when all prices decline.
• Do not choose the global minimum if it occurs after the sale.
• Do not use nested loops when the prefix minimum already summarizes all buy choices.

Recap

• Quadratic pair comparison is correct but inefficient.
• Decreasing input naturally returns zero.
• Preserve order and maintain only the two necessary summaries.

Learning goal: Justify the efficiency and correctness of the one-pass stock algorithm.

Core idea The loop visits each price exactly once. Each visit performs a constant amount of work: one minimum comparison, one subtraction, and one maximum comparison. Only minPrice and bestProfit are retained, so the extra memory does not grow with the input.

Algorithm plan

• Maintain the invariant that minPrice is the cheapest price in the scanned prefix.
• Maintain the invariant that bestProfit is the best valid profit in that prefix.
• When the scan ends, the prefix is the entire array, so bestProfit is globally optimal.

Micro-example For six prices, the loop performs six iterations, regardless of how many buy/sell pairs exist. The answer remains 5 while the stored state has constant size.

Pitfalls

• State the time as O(n), not O(n²).
• State auxiliary space as O(1); the input array itself is not extra workspace.
• Remember that one transaction means one buy and one later sell.

Recap

• Time complexity: O(n).
• Auxiliary space complexity: O(1).
• Running minimum plus best profit is the complete solution pattern.