Best Time to Buy and Sell Stock

Problem

Given an array of stock prices by day, find the maximum profit from buying on one day and selling on a later day. Return 0 if no profit is possible.

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5   (buy at 1, sell at 6)

Python Solution

def max_profit(prices):
    min_price = prices[0]
    best_profit = 0
    for price in prices[1:]:
        best_profit = max(best_profit, price - min_price)
        min_price = min(min_price, price)
    return best_profit

C++ Solution

int maxProfit(vector<int>& prices) {
    int minPrice = prices[0], bestProfit = 0;
    for (int i = 1; i < prices.size(); i++) {
        bestProfit = max(bestProfit, prices[i] - minPrice);
        minPrice = min(minPrice, prices[i]);
    }
    return bestProfit;
}

Java Solution

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = prices[0], bestProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            bestProfit = Math.max(bestProfit, prices[i] - minPrice);
            minPrice = Math.min(minPrice, prices[i]);
        }
        return bestProfit;
    }
}

Complexity

Time: O(n) — one pass tracking the lowest price seen so far. Space: O(1) — two running variables only.