Best Time to Buy and Sell Stock

Problem

Given an array where prices[i] is the price of a stock on day i, return the maximum profit you can achieve by buying on one day and selling on a later day. Return 0 if no profit is possible.

Input: [7, 1, 5, 3, 6, 4]  → 5   (buy at 1, sell at 6)
Input: [7, 6, 4, 3, 1]     → 0   (prices only fall)
Input: [1, 2]               → 1

Solution

Approach - single-pass running minimum.

The brute force checks every (buy, sell) pair, which is O(n²). The key reframing is to fix the sell day and ask: if I sell today, what is the best I could have done? The answer is today's price - the cheapest price seen on any earlier day. So you only need one number carried forward as you scan: min_price, the lowest price up to and including the current day. At each step you compute the profit of selling today against that minimum and keep the best you have ever seen in max_profit.

The order inside the loop matters. You update max_profit first, using the min_price from days strictly before today, then lower min_price if today is cheaper. This enforces buy-before-sell: the minimum you sell against can never include the current day as a same-day buy-and-sell with itself, and min_price only ever reflects past prices because you scan left to right. Trace [7, 1, 5, 3, 6, 4]: min starts at 7. At price 1 profit is negative so max stays 0, then min drops to 1. At 5 profit is 4, at 3 profit 2, at 6 profit 5 (the best), at 4 profit 3. Return 5.

Edge cases - a strictly falling series like [7, 6, 4, 3, 1] never produces a positive profit, so max_profit stays at its initial 0 - you simply choose not to trade.

Complexity - O(n) time, O(1) space - one pass tracking two scalars.