Best Time to Buy and Sell Stock

PracticeNeetCode ↗LeetCode ↗

Given an array prices where prices[i] is the price of a stock on day i, find the maximum profit from buying on one day and selling on a later day. Return 0 if no profit is possible.

Example

Key Pointers

• Track the lowest price seen so far as you scan — that's always the best possible buy point for any sale considered after it.
• One pass is enough; there's no need to check every buy/sell pair.
• A day's profit can come out negative relative to the running minimum — only keep it if it beats the current best.

Step-by-Step Analysis

1. Initialize min_price to infinity and max_profit to 0.
2. For each price: if it's lower than min_price, update min_price.
3. Otherwise, compute profit = price - min_price and update max_profit if it's larger.
4. Return max_profit.

Complexity

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

Code

def maxProfit(prices: list[int]) -> int:
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        else:
            max_profit = max(max_profit, price - min_price)
    return max_profit

Code Explanation

How the solution above works, piece by piece.

1. min_price = the cheapest day so far (the best day to have bought); max_profit starts at 0 because not trading is allowed.
2. For each day: if today's price is a new minimum, update min_price. Selling on the day you buy earns nothing, so there's nothing else to do.
3. Otherwise, selling today would earn price - min_price; keep it if it beats the best so far.
4. One pass, two variables: O(n) time, O(1) space.

Visual Walkthrough

Running it on prices = [7, 1, 5, 3, 6, 4]:

Video Explanation

Striver (takeUforward) — Best Time to Buy and Sell Stock, Brute-Optimal