Skip to content
LEETFLIX

Best Time to Buy and Sell Stock

EasyArrayDP
Solve on LeetCode

Buy low, sell high — but only in that order. A one-pass running minimum solves it.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

You are given an array prices where prices[i] is the price of a given stock on the i-th day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Constraints

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

Examples

Input

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

Output

5

prices

701152336445▲buy▲sell

Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 − 1 = 5. Buying at 7 and selling at 1 is not allowed because you must buy before you sell.

02

Solution

2 approaches · Python and Go. Pick a tab — the walkthrough follows.

Optimal▶ Animated

Sweep left to right; each day either lowers the minimum or tries to improve the best profit.

Carry min_price (cheapest day so far) and best (largest profit so far). On each day, if the price is a new low, it's a better place to buy — remember it. Otherwise, see what selling today at the recorded minimum would earn and keep the max.

A day can't be both a new minimum and a profitable sell (selling at the minimum yields ≤ 0), which is why the two branches are an if / elif.

Algorithm

  1. min_price = +∞, best = 0.
  2. For each price p: if p < min_price, set min_price = p.
  3. Else if p − min_price > best, set best = p − min_price.
  4. Return best.
Time
O(n)
Space
O(1)
Solution.py
class Solution:    def maxProfit(self, prices: list[int]) -> int:        min_price = float("inf")        best = 0        for p in prices:            if p < min_price:                min_price = p            elif p - min_price > best:                best = p - min_price        return best
Watch this run

03

Interactive walkthrough

Playing “One pass with a running minimum”. Edit the input, hit Run, then scrub.

Approach: One pass with a running minimum

Loading animation…

Up next

#53Maximum Subarray

Medium

Python · Go · Animated