Easy

Best Time to Buy and Sell Stock

013

Given prices where prices[i] is a stock price on day i, return the maximum profit from buying once and selling once on a later day. Return 0 if no profitable trade exists.

EXAMPLES

Example 1

Input
{
  "prices": [
    7,
    1,
    5,
    3,
    6,
    4
  ]
}

Output
5

FUNCTION SHAPE

prices: intArray→int

SOLUTION NOTE

Track minimum price seen so far. At each day, the best profit is selling at current price minus the minimum buy price.

Reveal reference solution +

pythonREFERENCE

def maxProfit(self, prices: List[int]) -> int:
    min_price, max_profit = inf, 0
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

TimeO(n)

SpaceO(1)

Open on LeetCode ↗