121. Best Time to Buy and Sell Stock (Easy)

Problem

Given an array prices where prices[i] is the price of a stock on day i, choose a single day to buy and a later day to sell to maximize profit. Return the maximum profit you can achieve; if no profit is possible, return 0.

Example

prices = [7, 1, 5, 3, 6, 4] → 5 (buy at 1, sell at 6)
prices = [7, 6, 4, 3, 1] → 0

LeetCode 121 · Link · Easy

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, every pair

Try all (buy_day, sell_day) with buy_day < sell_day.

def max_profit(prices: list[int]) -> int:
    n = len(prices)
    best = 0
    for i in range(n):                               # L1: outer loop, n iterations
        for j in range(i + 1, n):                   # L2: inner loop, up to n-i-1 iterations
            best = max(best, prices[j] - prices[i]) # L3: O(1) arithmetic + max
    return best

function maxProfit(prices: number[]): number {
    const n = prices.length;
    let best = 0;
    for (let i = 0; i < n; i++) {                              // L1: outer loop, n iterations
        for (let j = i + 1; j < n; j++) {                     // L2: inner loop, up to n-i-1
            best = Math.max(best, prices[j] - prices[i]);     // L3: O(1) arithmetic + max
        }
    }
    return best;
}

func maxProfit(prices []int) int {
  n := len(prices)
  best := 0
  for i := 0; i < n; i++ {                              // L1: outer loop, n iterations
    for j := i + 1; j < n; j++ {                      // L2: inner loop, up to n-i-1
      if prices[j]-prices[i] > best {               // L3: O(1) arithmetic + max
        best = prices[j] - prices[i]
      }
    }
  }
  return best
}

final class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var best = 0
        for buy in prices.indices {
            for sell in prices.indices where sell > buy { best = max(best, prices[sell] - prices[buy]) }
        }
        return best
    }
}

Where the time goes, line by line

Variables: n = len(prices).

Line	Per-call cost	Times executed	Contribution
L1 (outer loop)	$O(1)$	n	$O(n)$
L2/L3 (inner loop)	$O(1)$	n(n-1)/2	$O(n²)$ ← dominates

Every pair (buy_day, sell_day) with buy_day < sell_day is evaluated once. There are n(n-1)/2 such pairs, giving the $O(n²)$ total.

Complexity

Time: $O(n²)$ , driven by L2/L3 (the $O(n²)$ inner loop pairs).
Space: $O(1)$ .

Clear, correct, slow.

Approach 2: Prefix min array

Precompute, for each day, the minimum price seen so far. Then one pass to compute the max of prices[i] - min_so_far[i].

def max_profit(prices: list[int]) -> int:
    n = len(prices)
    if n < 2:
        return 0
    min_so_far = [prices[0]] * n           # L1: O(n) allocation
    for i in range(1, n):                  # L2: first pass, n-1 iterations
        min_so_far[i] = min(min_so_far[i - 1], prices[i])  # L3: O(1) per step
    return max(prices[i] - min_so_far[i] for i in range(n))  # L4: O(n) second pass

function maxProfit(prices: number[]): number {
    const n = prices.length;
    if (n < 2) return 0;
    const minSoFar = new Array<number>(n).fill(prices[0]);  // L1: O(n) allocation
    for (let i = 1; i < n; i++) {                           // L2: first pass, n-1 iterations
        minSoFar[i] = Math.min(minSoFar[i - 1], prices[i]);// L3: O(1) per step
    }
    let best = 0;
    for (let i = 0; i < n; i++) {                           // L4: O(n) second pass
        best = Math.max(best, prices[i] - minSoFar[i]);
    }
    return best;
}

func maxProfit(prices []int) int {
  n := len(prices)
  if n < 2 {
    return 0
  }
  minSoFar := make([]int, n)                        // L1: O(n) allocation
  minSoFar[0] = prices[0]
  for i := 1; i < n; i++ {                          // L2: first pass, n-1 iterations
    if prices[i] < minSoFar[i-1] {               // L3: O(1) per step
      minSoFar[i] = prices[i]
    } else {
      minSoFar[i] = minSoFar[i-1]
    }
  }
  best := 0
  for i := 0; i < n; i++ {                          // L4: O(n) second pass
    if prices[i]-minSoFar[i] > best {
      best = prices[i] - minSoFar[i]
    }
  }
  return best
}

final class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        guard let first = prices.first else { return 0 }
        var minimums = Array(repeating: first, count: prices.count)
        for index in prices.indices.dropFirst() { minimums[index] = min(minimums[index - 1], prices[index]) }
        return prices.indices.reduce(0) { max($0, prices[$1] - minimums[$1]) }
    }
}

Where the time goes, line by line

Variables: n = len(prices).

Line	Per-call cost	Times executed	Contribution
L1 (allocate array)	$O(n)$	1	$O(n)$
L2/L3 (prefix min pass)	$O(1)$	n-1	$O(n)$ ← tied for dominance
L4 (max profit pass)	$O(1)$	n	$O(n)$ ← tied for dominance

Two linear scans of the same array. The $O(n)$ space for min_so_far is the only cost beyond $O(1)$ .

Complexity

Time: $O(n)$ , driven by L2/L3 and L4 (two linear passes).
Space: $O(n)$ for the prefix array.

Approach 3: Single pass with running min (optimal)

Track the minimum price seen so far and the best profit, in one pass.

def max_profit(prices: list[int]) -> int:
    lowest = float('inf')             # L1: O(1)
    best = 0                          # L2: O(1)
    for price in prices:              # L3: single loop, n iterations
        if price < lowest:            # L4: O(1) comparison
            lowest = price            # L5: O(1) update buy candidate
        else:
            best = max(best, price - lowest)  # L6: O(1) profit check
    return best

function maxProfit(prices: number[]): number {
    let lowest = Infinity;                    // L1: O(1)
    let best = 0;                             // L2: O(1)
    for (const price of prices) {            // L3: single loop, n iterations
        if (price < lowest) {                // L4: O(1) comparison
            lowest = price;                  // L5: O(1) update buy candidate
        } else {
            best = Math.max(best, price - lowest);  // L6: O(1) profit check
        }
    }
    return best;
}

func maxProfit(prices []int) int {
  lowest := 1<<63 - 1                      // L1: O(1)
  best := 0                                // L2: O(1)
  for _, price := range prices {           // L3: single loop, n iterations
    if price < lowest {                  // L4: O(1) comparison
      lowest = price                   // L5: O(1) update buy candidate
    } else if price-lowest > best {      // L6: O(1) profit check
      best = price - lowest
    }
  }
  return best
}

final class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        guard let first = prices.first else { return 0 }
        var minimum = first, best = 0
        for price in prices.dropFirst() { best = max(best, price - minimum); minimum = min(minimum, price) }
        return best
    }
}

Where the time goes, line by line

Variables: n = len(prices).

Line	Per-call cost	Times executed	Contribution
L1/L2 (init)	$O(1)$	1	$O(1)$
L3 (loop)	$O(1)$ body	n	$O(n)$ ← dominates
L4/L5 (update min)	$O(1)$	at most n	$O(n)$
L6 (profit check)	$O(1)$	at most n	$O(n)$

One pass, two variables. L5 and L6 are mutually exclusive per iteration (either we found a cheaper buy, or we try a sell), so neither has hidden costs.

Complexity

Time: $O(n)$ , driven by L3 (one linear pass).
Space: $O(1)$ .

Why it’s a sliding window

left marks the buy day (always the minimum seen so far); right sweeps forward. When a better buy day appears, left jumps to it. Each day is visited once; the window width is variable.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Every pair	$O(n²)$	$O(1)$
Prefix min array	$O(n)$	$O(n)$
Running min + profit	$O(n)$	$O(1)$

The single-pass template generalizes to many “best X after running min/max” problems (including Maximum Subarray, also known as Kadane’s).

Test cases

# Quick smoke tests - paste into a REPL or save as test_121.py and run.
# Uses the optimal Approach 3 implementation.

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

def _run_tests():
    assert max_profit([7, 1, 5, 3, 6, 4]) == 5    # buy at 1, sell at 6
    assert max_profit([7, 6, 4, 3, 1]) == 0        # strictly decreasing, no profit
    assert max_profit([1]) == 0                    # single price, can't sell
    assert max_profit([1, 2]) == 1                 # two prices, simple profit
    assert max_profit([2, 4, 1]) == 2              # profit before the new low
    assert max_profit([3, 3, 3]) == 0              # all same price
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function maxProfit(prices: number[]): number {
    let lowest = Infinity;
    let best = 0;
    for (const price of prices) {
        if (price < lowest) lowest = price;
        else best = Math.max(best, price - lowest);
    }
    return best;
}

console.assert(maxProfit([7, 1, 5, 3, 6, 4]) === 5);
console.assert(maxProfit([7, 6, 4, 3, 1]) === 0);
console.assert(maxProfit([1]) === 0);
console.assert(maxProfit([1, 2]) === 1);
console.assert(maxProfit([2, 4, 1]) === 2);
console.assert(maxProfit([3, 3, 3]) === 0);
console.log("all tests pass");

func maxProfit(prices []int) int {
  lowest := 1<<63 - 1
  best := 0
  for _, price := range prices {
    if price < lowest {
      lowest = price
    } else if price-lowest > best {
      best = price - lowest
    }
  }
  return best
}

Arrays, input; running-min sliding window

Array Scans, the linear pass habit of carrying just enough state while reading each item once.
Greedy Algorithms, the local choice pattern protected by an invariant about the best reachable future.

121. Best Time to Buy and Sell Stock (Easy)

Problem

Try it yourself

Approach 1: Brute force, every pair

Approach 2: Prefix min array

Approach 3: Single pass with running min (optimal)

Why it’s a sliding window

Summary

Test cases

Related data structures

Related concepts