Skip to main content
DSA patterns

Best Time to Buy and Sell Stock

easySliding window Must-doAmazonPhonePeRazorpay

Problem statement

You're given an array prices, where prices[i] is a value recorded on day i. Pick one day to "buy" at that day's value and a later day to "sell" at that day's value, so as to maximize the difference between the sell value and the buy value. If no later day is ever higher than an earlier one, the best you can do is make no move at all, for a profit of 0.

This is the same shape as scanning a metric over time — CPU price on a spot instance, or a queue depth reading — to find the largest rise from an earlier low point to a later high point, without ever looking into the future to pick your "buy" day.

Examples

Example 1

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

Output: 5

Explanation: Buying at day 1 (price 1) and selling at day 4 (price 6) gives a profit of 6 - 1 = 5. No other buy-then-sell pair in the array does better.

Example 2

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

Output: 0

Explanation: Every later day has a lower price than every earlier day, so no buy-then-sell pair makes a profit — the best choice is to make no transaction, for a profit of 0.

Hints

Hint 1: Checking every possible buy day and sell day works, but with up to 10^5 days, that's up to about 5 billion pairs to check — too slow.

Approach

Optimal: Track the running minimum

Intuition

You never need to compare a day against every earlier day individually — you only ever care about the lowest price seen before it, since that's the buy day that would give the best possible profit for any given sell day. So walk through the prices once: keep track of the lowest price seen so far, and at each day, check what profit you'd get by selling today against that lowest price. That turns the brute force's full pairwise scan into one pass, which is what makes it faster.

Steps

  1. Set minPrice to infinity (or the first price) and best to 0.
  2. For each price in the array, in order:
    • If price is lower than minPrice, update minPrice to price (a new best day to "buy").
    • Otherwise, check if price - minPrice is bigger than best, and update best if so (a potential "sell" today).
  3. Return best.

Dry run

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

price minPrice before action profit if sold today best after
7 ∞ 7 < ∞ → minPrice = 7 — 0
1 7 1 < 7 → minPrice = 1 — 0
5 1 5 ≥ 1 → check profit 5 - 1 = 4 4
3 1 3 ≥ 1 → check profit 3 - 1 = 2 4
6 1 6 ≥ 1 → check profit 6 - 1 = 5 5
4 1 4 ≥ 1 → check profit 4 - 1 = 3 5

The best profit found, 5, matches the example — buying on day 1 (price 1) and selling on day 4 (price 6).

Edge cases: an array of length 1 has no day after the first to sell on, so best correctly stays 0; when prices only fall (example 2), minPrice keeps updating to each new lower value and the profit check never beats 0, so the result is 0.

Complexity

Time O(n) - a single pass over the prices, doing constant work per day.

Space O(1) - just two running values: the lowest price seen so far and the best profit seen so far.

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = float("inf")
        best = 0
        for price in prices:
            if price < min_price:
                min_price = price
            elif price - min_price > best:
                best = price - min_price
        return best


if __name__ == "__main__":
    print(Solution().maxProfit([7, 1, 5, 3, 6, 4]))  # 5
    print(Solution().maxProfit([7, 6, 4, 3, 1]))  # 0
RecapThe whole problem in a few lines, for the night before
  • Spot it: "maximize profit from one buy then one later sell" over a sequence of values
  • Idea: walk through once, tracking the lowest value seen so far and the best profit against it
  • Cost: O(n) time, O(1) space
  • Trap: comparing every pair of days is O(n²) and too slow — only the running minimum before each day matters, not every earlier day individually

Interview follow-ups

  • What if you also needed to return which two days to buy and sell on, not just the profit?

    Keep two extra variables — the day index of the current minPrice and the day index of the best sell so far — updating them alongside minPrice and best inside the same loop. Still O(n) time and O(1) extra space, just two more variables tracked in step.

  • The prices arrive as a live stream and you need the best profit "so far" at any moment, not just at the end?

    The same running-minimum approach works incrementally: keep minPrice and best as persistent state, and update them each time a new price arrives, in O(1) time per price. That gives you an always-current answer without ever re-scanning the history, which is exactly what the single-pass approach already does — it just happens to also work online.

Frequently asked questions

For any given sell day, the best possible buy day is always the one with the lowest price among all the days before it — buying at a higher earlier price can never produce a better profit than buying at the lowest one. So instead of remembering every earlier price, you only need to remember the smallest one, and update it as you go.

Finding the largest rise from an earlier low point to a later high point in a single pass is the same shape as watching a time series — a spot-instance price, a queue length, a response-time metric — for the worst regression or the biggest recoverable dip, without scanning the whole history for every point. It's also a common warm-up for checking whether a candidate can recognize that a nested-loop brute force can collapse into one running-minimum pass.

That's a different, related problem (often called "Best Time to Buy and Sell Stock II"). The greedy idea there is to add up every single-day rise (prices[i+1] - prices[i] whenever it's positive), since any profitable multi-day rise can always be split into a chain of profitable one-day rises. This problem only allows a single buy and a single sell, which is why tracking one running minimum is enough.

Today's price can't be both a new record low and the best sell day against the previous low at the same time — if it's a new low, there's no profit to record yet (you'd be "selling" to yourself on the same day), and if it's not a new low, it's worth checking as a potential sell day. Structuring it as if / elif avoids doing a pointless profit check on the very day that becomes the new minimum.