Best Time to Buy and Sell Stock

NeetCode: Best Time to Buy and Sell Stock · LeetCode: 121. Best Time to Buy and Sell Stock · Difficulty: Easy

prices[i] (an int[]) is the price on day i. Choose one day to buy and a later day to sell to maximise profit. Return the best profit, or 0 if no profit is possible.

Example

Text

Input:  prices = [10, 1, 5, 6, 7, 1]    Output: 6    (buy at 1, sell at 7)
Input:  prices = [10, 8, 7, 5, 2]       Output: 0

Brute force: every buy/sell pair

Java

class Solution {
    public int maxProfit(int[] prices) {
        int best = 0;
        for (int buy = 0; buy < prices.length; buy++) {
            for (int sell = buy + 1; sell < prices.length; sell++) {
                best = Math.max(best, prices[sell] - prices[buy]);
            }
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxProfit(new int[] {10, 1, 5, 6, 7, 1}));
        System.out.println(s.maxProfit(new int[] {10, 8, 7, 5, 2}));
    }
}

Output

6
0

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

Optimal: track the cheapest price so far

For a fixed sell day, the best buy day is the cheapest day before it. So scan once, keeping the minimum price seen (starting from Integer.MAX_VALUE, which the first price replaces), and at each day compute the profit of selling that day. This is a sliding window whose left edge jumps to any new low.

Java

class Solution {
    public int maxProfit(int[] prices) {
        int lowest = Integer.MAX_VALUE;
        int best = 0;
        for (int price : prices) {
            lowest = Math.min(lowest, price);
            best = Math.max(best, price - lowest);
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxProfit(new int[] {10, 1, 5, 6, 7, 1}));
        System.out.println(s.maxProfit(new int[] {10, 8, 7, 5, 2}));
        System.out.println(s.maxProfit(new int[] {}));
    }
}

Output

6
0
0

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