Best Time to Buy and Sell Stock

Easysliding windowAmazonMetaGoogleGoldman Sachs

You are given an array prices where prices[i] is the price of a given stock on the ith 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.

Examples

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

Output:5

Explanation:Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

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

Output:0

Explanation:No profitable transaction is possible, so max profit is 0.

Constraints

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

💡 Hints

Hint 1

Track the minimum price seen so far as you scan left to right.

Hint 2

At each step, calculate the profit if you sold today (current price - min price). Track the maximum profit.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Linear

Algorithmic Approach

Single pass: track the minimum price seen so far and the maximum profit possible at each position. The sliding window is between the min price day and the current day.

Time ComplexityO(n)

Why:

A single pass through the prices array updates the minimum buy price and maximum profit in O(1) per day.

Space ComplexityO(1)

Why:

Only a few scalar tracking variables (minPrice, maxProfit) are maintained.

Big-O Growth CurveLinear (O(N))

Execution time scales directly in proportion to the input size.

🌍 Real-World Use Cases

Goldman SachsTrading algorithms

Finding the optimal buy-low-sell-high opportunity in historical stock data for backtesting trading strategies.

AmazonDynamic pricing

Analyzing historical price data to determine the best markdown-to-sale timing for maximum revenue per product.

🔍 Dry Run

Solution⏱ O(n) | 💾 O(1)

Line2

minPrice=∞number

maxProfit=0number

i=0number

Initialize minPrice=∞, maxProfit=0. Start scanning at i=0 (price 7)