Best Time to Buy and Sell Stock

The array prices lists the price of one share of a stock on consecutive days: prices[i] is the price on day i.

You may make at most one trade: buy a single share on one day and sell it on a strictly later day. Your profit is the selling price minus the buying price.

Return the largest profit you can achieve. If no trade makes money, return 0 (you simply do not trade).

Example 1

Example 2

Example 3

Constraints

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

Pattern Path · Intervals & Greedy · problem 108 of 169

Start simple

Try every pair of days (buy i, sell j > i) with two nested loops and keep the best difference: O(n²) time, O(1) space.

The key idea

Think about each day as a potential selling day. If you sell on day j, the best you can do is to have bought at the cheapest price on any day before j. So the whole problem reduces to knowing the minimum of a prefix, and a prefix minimum can be maintained in O(1) per step.

Scan the prices from left to right with two variables: lowest, the cheapest price seen so far, and best, the largest profit found so far. For each price, first update lowest, then compare price - lowest with best. Updating the minimum before computing the profit is safe: on a new minimum the candidate profit is 0, which never beats a non-negative best.

Note that a new minimum does not reset best. In [4, 9, 1, 3] the cheapest day comes late, but the winning trade (4 then 9) happened earlier and must be kept. Because best starts at 0, a steadily falling market correctly returns 0.

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def maxProfit(self, prices):
        lowest = float('inf')  # cheapest price seen so far
        best = 0               # best profit found so far (not trading earns 0)
        for price in prices:
            lowest = min(lowest, price)
            best = max(best, price - lowest)
        return best

JavaScript

var maxProfit = function(prices) {
  let lowest = Infinity; // cheapest price seen so far
  let best = 0;          // best profit found so far (not trading earns 0)
  for (const price of prices) {
    lowest = Math.min(lowest, price);
    best = Math.max(best, price - lowest);
  }
  return best;
};

What the interviewer is checking

The interviewer wants you to turn a pairwise O(n²) search into one pass by asking what single piece of history each step needs, here the running minimum.

Mistakes to avoid

• Returning max(prices) - min(prices): the minimum may come after the maximum, which is not a legal trade.
• Letting the answer go negative when prices only fall; the answer is never below 0.
• Resetting the best profit whenever a new minimum appears, which forgets an earlier, better trade.

Follow-ups to expect

• What if you may trade as many times as you like? (Sum every positive day-to-day rise.)
• What if you may make at most two trades? (Track four running states in one pass.)
• What if every trade pays a fixed fee? (DP over holding and not holding.)

In real software

Finding the largest gain or drawdown in a time series, such as a portfolio value or a server's latency history, uses the same running-minimum scan.

Practice next