121. Best Time to Buy and Sell Stock

Quick Identifier

• Topic: arrays-hashing
• Pattern: Running Minimum (Greedy One-Pass)
• Hint: You want to buy low and sell high, but time only moves forward. As you look at today's price, ask yourself: "If I had to sell today, what is the cheapest price I could have bought at in the past?"
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Microsoft, Bloomberg
• LeetCode: 121

Quick Sights

• Time Complexity: O(n). We iterate through the array of prices exactly once.
• Space Complexity: O(1). We only maintain two variables: the minimum price seen so far, and the maximum profit calculated so far.
• Core Mechanism: Iterate through the prices. Update minPriceSoFar if today's price is lower than any price seen before. Simultaneously, calculate the profit if you sold today (todayPrice - minPriceSoFar). If this profit is greater than your maxProfit, update maxProfit.

Concept Explanation

As a senior engineer, don't just memorize the code—understand the temporal restriction. You cannot sell before you buy. This makes it a State Tracking problem.

1. The Brute Force Trap: The naive approach is checking every pair of days: "Buy on Day 1, sell on Day 2, 3, 4... Buy on Day 2, sell on Day 3, 4...". This is $O(n^2)$ and ignores the flow of time.
2. The "Hindsight" Invariant: Imagine looking back in time from the current day. If you sell today, your maximum possible profit is strictly bound by the absolute lowest price that occurred at any time before today.
3. The Single Pass: Because both "current day" and "lowest price before current day" can be tracked simultaneously as you scan left-to-right, you can collapse the $O(n^2)$ loops into an $O(n)$ single pass.
   • For every day: What is my profit if I sell today? profit = price - minPrice.
   • After checking profit: Is today the new lowest price ever seen? minPrice = min(minPrice, price).

Diagram

This flowchart outlines the greedy single-pass state tracking.

Study Pattern (SDE3+)

• 0–3 min: This is a foundational question. Immediately verbalize the $O(n)$ state-tracking solution. State that the problem is functionally identical to finding the maximum positive delta in a time series.
• Implementation pass: Order of operations matters slightly. While not strictly required, it's logically cleaner to calculate the profit before updating minPrice. Why? Because you can't buy and sell on the exact same day for a profit. (Though mathematically price - price = 0, which won't overwrite a positive maxProfit, it's better to reflect chronological reality).
• 5 min extension: Relate this to Kadane's Algorithm (Maximum Subarray). Explain that if you convert the prices array into an array of daily changes (deltas), finding the max profit is mathematically identical to finding the maximum contiguous subarray sum of those deltas.

Approaches

• Brute force — Check every $i, j$ pair where $i < j$. Time: $O(n^2)$, Space: $O(1)$.
• Running Minimum — Track the minimum price seen so far. Time: $O(n)$, Space: $O(1)$. (Always pick this)

Optimal Solution

Go

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}

	minPrice := prices[0]
	maxProfit := 0

	for i := 1; i < len(prices); i++ {
		price := prices[i]

		// What would our profit be if we sold today?
		currentProfit := price - minPrice
		if currentProfit > maxProfit {
			maxProfit = currentProfit
		}

		// Is today the best day to buy for the future?
		if price < minPrice {
			minPrice = price
		}
	}

	return maxProfit
}

JavaScript

function maxProfit(prices) {
	if (prices.length === 0) return 0;

	let minPrice = prices[0];
	let maxProfit = 0;

	for (let i = 1; i < prices.length; i++) {
		const price = prices[i];

		// Update max profit if selling today is better
		maxProfit = Math.max(maxProfit, price - minPrice);

		// Update min price if today is cheaper
		minPrice = Math.min(minPrice, price);
	}

	return maxProfit;
}

Walkthrough

Input: prices = [7, 1, 5, 3, 6, 4]

Output: 5 (Buy at 1, sell at 6).

Edge Cases

• Array is strictly decreasing (e.g., [7, 6, 4, 3, 1]). Profit will never exceed 0, safely returns 0.
• Array length is 1 or 0. Loop never runs or returns early, safely returns 0.
• Array is strictly increasing. minPrice stays at index 0, maxProfit updates every single day, returning the max possible delta.

Pitfalls

• Calculating price - minPrice after updating minPrice. As stated earlier, this forces the algorithm to "buy and sell" on the exact same day. While it doesn't break the logic here (because profit is 0 and won't overwrite a positive max), it breaks conceptually in variants involving transaction fees.

Similar Problems

• 122. Best Time to Buy and Sell Stock II — Unlimited transactions allowed.
• 053. Maximum Subarray — Maximum subarray sum (mathematically equivalent to stock deltas).
• 42. Trapping Rain Water — A more advanced two-pointer state tracking problem.

Mind-Map Tags

#arrays #greedy #running-minimum #state-tracking #stock