Best Time to Buy and Sell Stock

The key idea

Scan left to right tracking the smallest price seen so far. For each day, the best profit ending today is today's price minus that running minimum. Keep the largest such profit. You never need to look back, because the cheapest buy day is always behind you.

Problem

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

Input: prices = [7,6,4,3,1] Output: 0

Complexity

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

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →