121. Best Time to Buy and Sell Stock

At a Glance

• Topic: arrays-hashing
• Pattern: One pass minimum (single transaction)
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Microsoft, Bloomberg
• Frequency: Very High
• LeetCode: 121

Problem (one-liner)

Given daily prices prices, choose one buy day before one sell day to maximize profit sell - buy. Return that maximum profit, or 0 if no gain is possible.

Recognition Cues

• "One buy one sell", "maximize profit"
• Track minimum price seen so far; profit if sold today

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — all pairs — O(n²) time.
• Better — scan left minima — O(n) time / O(1) space.
• Optimal — same single pass: bestProfit = max(price - minPriceSoFar) — O(n) time / O(1) space.

Optimal Solution

Go

package main

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	minPriceSoFar := prices[0]
	bestProfit := 0
	for dayIndex := 1; dayIndex < len(prices); dayIndex++ {
		price := prices[dayIndex]
		if price-minPriceSoFar > bestProfit {
			bestProfit = price - minPriceSoFar
		}
		if price < minPriceSoFar {
			minPriceSoFar = price
		}
	}
	return bestProfit
}

JavaScript

function maxProfit(prices) {
	if (prices.length === 0) {
		return 0;
	}
	let minPriceSoFar = prices[0];
	let bestProfit = 0;
	for (let dayIndex = 1; dayIndex < prices.length; dayIndex++) {
		const price = prices[dayIndex];
		bestProfit = Math.max(bestProfit, price - minPriceSoFar);
		minPriceSoFar = Math.min(minPriceSoFar, price);
	}
	return bestProfit;
}

Walkthrough

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

Answer 5 (buy at 1, sell at 6).

Edge Cases

• Monotonic decreasing — profit 0.
• Two days — simple comparison.
• Duplicate prices — min tracking handles.

Pitfalls

• Selling before buying — enforced by updating min after profit check order (or equivalent logic).
• Allowing multiple transactions when problem asks one (see Stock II).

Similar Problems

• 122. Best Time to Buy and Sell Stock II — unlimited transactions.
• 053. Maximum Subarray — profits as differences form subarray problem variant.
• 189. Rotate Array — array reasoning practice.

Variants

• Cooldown / fee per transaction — DP states.
• At most k transactions — DP.

Mind-Map Tags

#arrays #greedy #min-so-far #profit #one-pass