Brute Force
Time O(n²)Space O(1)Try every pair of buy day i and sell day j > i, and keep the best prices[j] - prices[i]. Correct, but it recomputes the same subtractions over and over.
class Solution: def maxProfit(self, prices: list[int]) -> int: best = 0 n = len(prices) for i in range(n): for j in range(i + 1, n): best = max(best, prices[j] - prices[i]) return bestO(n²) pairs checked — too slow once n approaches 10^5.
One Pass (Track Minimum)
OptimalTime O(n)Space O(1)The best sell day is always paired with the lowest price seen so far to its left — there’s never a reason to buy at a higher earlier price. So walk once, tracking the minimum price seen and the best profit achievable by selling today.
class Solution: def maxProfit(self, prices: list[int]) -> int: min_price = float('inf') best = 0 for price in prices: min_price = min(min_price, price) best = max(best, price - min_price) return bestTracing prices = [7,1,5,3,6,4] shows the running low and the best trade evolving together:
Price by day
Lowest seen
—
none
Gain today
—
waiting
Best
0
none yet
Best trade recorded
Six prices, one pass. Track the lowest price seen so far, then ask on every day: what would selling today gain? The first day is next.
Why it’s correct: at each day, the only decision that matters is “what’s the cheapest I could have bought for by now?” — everything else is dominated. Complexity: single pass, constant extra space → O(n) time, O(1) space, and this is optimal since you must look at every price at least once.