LeetEye LeetEye
Medium Sliding Window ~5 min

Best Time to Buy and Sell Stock

sliding-window best-time-to-buy-and-sell-stock

Problem

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

Example 1
Input: prices = [7,1,5,3,6,4]
Output: 5
Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Example 2
Input: prices = [7,6,4,3,1]
Output: 0
No profitable transaction possible (prices only decrease).
Key Insight

Track the minimum price seen so far. At each day, calculate potential profit if we sold today.

Track minimum price seen. At each day, profit = today - min. Track maximum profit.

How to Approach This Problem

Pattern Recognition: When you see keywords like best time to buy and sell stock sliding-window, think Sliding Window.

Step-by-Step Reasoning

1 To find max profit, the naive approach is:
Answer: For each day, check profit with every future day
We need to check all buy-sell pairs where sell comes after buy. But this is O(n²).
2 Given prices = [3, 1, 4], after sorting = [1, 3, 4]. Max - min = 4 - 1 = 3. Is this achievable?
Answer: Only if max comes after min in original array
We can only sell AFTER buying. Sorting loses temporal order. Here it works (4 comes after 1), but [4,1,3] would give wrong answer.
3 As we scan left to right, what should we track?
Answer: Minimum price seen so far
We want to buy low. The best buy opportunity at any point is the minimum we've seen. We can only buy in the past, not the future.
4 At day i, the best profit if we sell today is:
Answer: prices[i] - min(prices[0:i])
Best profit = today's price minus the cheapest price before today.
5 After computing today's potential profit, we:
Answer: Update answer if this profit > current best
We want maximum profit, so only update if we found a better one.
6 If today's price is lower than our tracked minimum:
Answer: We should update minimum, and profit today is 0
New minimum can't give positive profit today (selling at price we just bought). Future days might benefit from this lower buy price.

Solution

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

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Sliding Window problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye