Best Time to Buy and Sell Stock

Given daily stock prices, find the maximum profit from buying on one day and selling on a later day (or 0 if no profit is possible).

EasyMust DoRunning MinimumLeetCode

Why solve this?

It's the simplest introduction to tracking a running best-so-far value in a single pass.

Pattern recognition

Whenever you need "the best result using an earlier value", track that earlier value's running minimum/maximum as you scan instead of comparing every pair.

Prerequisites

Arrays

Hints

A brute-force check of every buy/sell pair is O(n^2).
As you scan left to right, what's the lowest price you've seen so far?
At each day, the best possible profit if you sold today is today's price minus the running minimum.

Approach

Track `minPriceSoFar` as you scan the array once. At each day, the best profit achievable by selling today is `price[i] - minPriceSoFar`; keep a running `maxProfit` of that value, then update `minPriceSoFar` if today's price is lower. One pass, constant extra space.

Java solution

Solution.java

class Solution {
    public int maxProfit(int[] prices) {
        int minPriceSoFar = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            if (price < minPriceSoFar) {
                minPriceSoFar = price;
            } else if (price - minPriceSoFar > maxProfit) {
                maxProfit = price - minPriceSoFar;
            }
        }
        return maxProfit;
    }
}

Time: O(n)Space: O(1)