Sweaty Imposter

Best Time to Buy and Sell Stock

EasySliding WindowBlind 75JuniorOpen on LeetCodeUpdated

You're given an array prices where prices[i] is a stock's price on day i. You may make at most one trade: buy on one day and sell on a strictly later day. Return the maximum profit that trade can make. If no trade makes money, return 0, since you're allowed not to trade at all.

Examples

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

715364
Buy on day 1 at 1, sell on day 4 at 6.

Buy at price 1 (index 1) and sell at price 6 (index 4) for a profit of 5. The 7 is higher, but it comes before the cheapest day, so you can't sell there.

prices = [7,6,4,3,1] returns 0

The price falls every day, so any sale would lose money. Not trading gives 0.

Constraints

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

Hints

Hint 1

If you knew you were selling today, which earlier day would you have wanted to buy on?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

The best sale on any day pairs with the cheapest price on an earlier day. Scan once, keeping the minimum price seen so far and the best profit. Each day is either a new low, which becomes the buy price for later days, or a chance to sell, earning price - min_so_far; keep the largest. Because best starts at 0, prices that only fall return 0.

Time

O(n)

Space

O(1)

Pitfall

Returning max(prices) - min(prices) ignores the order of days: for [7,1,5,3,6,4] it gives 6, but the 7 comes before the 1, so you can't sell there. The sale must come after the purchase.

Solutions

class Solution {
    public int maxProfit(int[] prices) {
        int minSoFar = Integer.MAX_VALUE;
        int best = 0;
        for (int p : prices) {
            if (p < minSoFar) minSoFar = p;
            else if (p - minSoFar > best) best = p - minSoFar;
        }
        return best;
    }
}
Drill This