AlgoMaster Logo

Best Time to Buy and Sell Stock

Last Updated: March 19, 2026

easy
3 min read

Understanding the Problem

At first glance, this seems like a simple "find the max difference" problem. And it almost is, but with one important constraint: the buy must happen before the sell. You can't just find the global minimum and global maximum and subtract them, because the minimum might come after the maximum.

For example, in [7, 6, 4, 3, 1], the minimum is 1 and the maximum is 7, but 7 comes before 1. You'd have to buy at 7 and sell at 1, which gives you a loss, not a profit.

So the real question is: for each day, what's the cheapest price we've seen on any previous day? If we know that, the profit from selling on that day is simply the current price minus the cheapest previous price. The answer is the maximum of all such profits.

Key Constraints:

  • 1 <= prices.length <= 10^5 → With up to 100,000 elements, we need O(n log n) or better. An O(n^2) brute force would mean up to 10^10 operations, which will time out.
  • 0 <= prices[i] <= 10^4 → Prices are non-negative integers. No need to handle negative values, and the difference between any two prices fits comfortably in a 32-bit integer.

Approach 1: Brute Force

Intuition

The most natural first attempt is to try every possible pair of buy and sell days. For each day i, we look at every future day j (where j > i), compute the profit prices[j] - prices[i], and keep track of the maximum.

This guarantees we find the answer because we're literally checking every valid transaction.

Algorithm

  1. Initialize maxProfit to 0 (if no profitable transaction exists, we return 0)
  2. For each day i from 0 to n-2 (potential buy day):
    • For each day j from i+1 to n-1 (potential sell day):
      • Compute profit = prices[j] - prices[i]
      • Update maxProfit if this profit is larger
  3. Return maxProfit

Example Walkthrough

1Initialize: i=0 (buy), j=1 (sell), maxProfit=0
0
i (buy)
7
1
1
j (sell)
2
5
3
3
4
6
5
4
1/7

Code

For each buy day i, we scan every future day j to find the best sell price. That inner scan is O(n) per buy day, leading to O(n^2) total. When we move from buy day i to buy day i+1, we throw away everything we learned about future prices and start scanning from scratch. But the best sell price for day i+1 overlaps heavily with what we already checked for day i.

What if instead of scanning forward from each buy day, we scanned once left to right and tracked the cheapest buy price we've seen so far?

Approach 2: One Pass (Optimal)

Intuition

The brute force does a lot of redundant work. For each sell day j, it scans backwards through all previous days to find the best buy price. But think about it: as we move from left to right, we can keep track of the minimum price we've seen so far. Then for each day, the best profit from selling on that day is simply currentPrice - minPriceSoFar.

Here's the key insight: we don't need to know which day had the minimum price. We just need the value itself. And since we're scanning left to right, the minimum is always from a day before the current one, which satisfies the "buy before sell" constraint automatically.

Algorithm

  1. Initialize minPrice to the first price (or infinity)
  2. Initialize maxProfit to 0
  3. For each price in the array:
    • If the current price is less than minPrice, update minPrice
    • Otherwise, compute profit = currentPrice - minPrice and update maxProfit if larger
  4. Return maxProfit

Example Walkthrough

1Initialize: minPrice=INF, maxProfit=0, start scanning
0
7
i
1
1
2
5
3
3
4
6
5
4
1/8

Code