Sliding Window · LC #121

Best Time to Buy and Sell Stock

Track the running minimum price seen so far; for each day compute potential profit (price − minPrice) and update the global maximum. Classic greedy single-pass pattern.

easyLC #121AMZ★★★GOO★★★META★★★MSFT★★★AAPL★★
Mark as done
Confidence
Ask GPTPractice

Statement

Problem & Approach

Problem statement, sample I/O, and key reasoning.

Given array `prices` where `prices[i]` is the stock price on day `i`, return the maximum profit from one buy and one sell (buy before sell). Return 0 if no profit is possible.

Sample I/O

Input:  prices = [7,1,5,3,6,4]
Output: 5   (buy day 2 at 1, sell day 5 at 6)

Input:  prices = [7,6,4,3,1]
Output: 0   (always falling, no profit)

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

Intuition

How to Think About It

Intuition

If you knew the cheapest price in all days before today, the best profit you could make today is (today's price − cheapest historical price). Scan left to right: maintain the minimum price seen so far; at each price compute the profit if you sold today; track the maximum.

Core Concept

Single pass: min_price = inf, max_profit = 0. For each price p: min_price = min(min_price, p); max_profit = max(max_profit, p - min_price). Return max_profit. Time O(n), Space O(1). This is equivalent to a two-pointer where the left pointer (buy day) only moves forward when a new minimum is found.

When to use

Single-transaction stock profit maximisation. Generalises to "maximum subarray maximum-minus-previous-minimum" pattern. Related to Kadane's algorithm conceptually.

When NOT to use

When multiple transactions are allowed (LC 122 - greedy sum of positive differences). When k transactions are allowed (LC 188 - DP). When short selling is required.

Key Insights

What to Know Cold

  • You never need to look backward: the running minimum captures all information about the best buy price seen so far.
  • This is equivalent to finding the maximum of prices[j] − prices[i] for all i < j - a classic max-difference problem.
  • Kadane's algorithm on the difference array (daily returns) solves the same problem: max subarray sum of price differences.
  • The answer is always ≥ 0 because we can choose not to trade (buy = sell day, profit = 0).
  • Two-pointer view: l (buy) advances only when a cheaper price is found; r (sell) advances every day.

1 example

Worked Examples

Running-minimum greedy - Python

Find max single-transaction profit in [7,1,5,3,6,4].

Track min_price so far; each iteration compute profit if sold today.

def maxProfit(prices: list[int]) -> int:
    min_price, max_profit = float('inf'), 0
    for p in prices:
        min_price = min(min_price, p)
        max_profit = max(max_profit, p - min_price)
    return max_profit
# [7,1,5,3,6,4] → 5

Output: 5

Ubiquitous interview problem; tests ability to reduce an O(n²) brute-force to O(n) by maintaining a single running variable.