Best Time to Buy and Sell Stock

Difficulty: Easy

Problem

You have a list prices where prices[i] is what a stock costs on day i. Pick one day to buy and a later day to sell so that your gain is as large as possible, and return that gain. The purchase has to come before the sale.

Example

Input: prices = [9, 4, 8, 2, 10, 6]
Output: 8
Explanation: Buy on day 4 (price = 2) and sell on day 5 (price = 10) for a profit of 10-2 = 8. Buying on day 2 at 4 would only reach 6.

Brute-force approach

Try every pair of buy and sell days to find maximum profit.

Steps

  1. For each buy day i
  2. Try every sell day j > i
  3. Calculate profit = prices[j] - prices[i]
  4. Track maximum profit

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Checking all pairs is slow
  • Many pairs are clearly suboptimal
  • Don't need to check all

Optimal approach

Key insight: Best profit at any day = today's price - minimum price seen before today.

Track minimum price seen so far. At each price, check if selling now gives better profit.

Steps

  1. Track minimum price seen
  2. At each price, update min if smaller
  3. Calculate profit if selling today
  4. Track maximum profit

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

Pseudocode

function maxProfit(prices):
    minPrice = infinity
    maxProfit = 0
    
    for each price in prices:
        if price < minPrice:
            minPrice = price
        else if price - minPrice > maxProfit:
            maxProfit = price - minPrice
    
    return maxProfit

Hints

  • Track the minimum price seen so far
  • At each day, calculate potential profit if we sell today
  • Keep track of the maximum profit

Complexity questions

Time to check all buy/sell pairs?

O(n²). n choices for buy × n choices for sell = O(n²)

Time for one-pass solution?

O(n). One pass through array, constant work each step = O(n)

Space for both approaches?

O(1). Only tracking min price and max profit = O(1)

How is this related to sliding window?

Buy point as left, sell as right - window expands. Left pointer = buy day (always at min), right = current day. Window expands right.

Check your understanding of Best Time to Buy and Sell Stock

What's the goal of this problem?

Maximize profit from one buy and sell. Find the maximum profit from buying on one day and selling on a later day.

Given [7,1,5,3,6,4], what's the max profit?

5. Buy at 1, sell at 6 = profit of 5

Related problems

Keep practising