Best Time to Buy and Sell Stock
You are given an array `prices` where `prices[i]` is the stock price on day `i`. You may buy on one day and sell on a strictly later day. Return the maximum profit possible, or `0` if no profitable transaction exists. **Core Insight:** We want to find the largest difference `prices[j] - prices[i]` where `j > i`. Instead of checking every pair (O(n²)), we track the minimum price seen so far as we scan left to right. At each day, the best profit we could make selling today is `prices[i] - minSoFar`. We update our answer with this value and also update `minSoFar` if the current price is lower. **Algorithm:** Single pass. Maintain `minPrice = Infinity` and `maxProfit = 0`. For each price: update `minPrice`, then update `maxProfit = max(maxProfit, price - minPrice)`. **Complexity:** Time O(n) — one pass. Space O(1) — two variables.
Constraints
- •
1 ≤ prices.length ≤ 10⁵ - •
0 ≤ prices[i] ≤ 10⁴
def maxProfit(prices: list[int]) -> int:
min_price = float('inf')
max_profit = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_profit:
max_profit = price - min_price
return max_profit