Difficulty: Easy · LeetCode 121

Problem

Find maximum profit from buying on one day and selling on a future day.

Understanding the problem

Profit = price[sell] - price[buy] where sell > buy.

Intuition

Track the minimum price seen so far while scanning rightward.

Approach

Track min_price = infinity and max_profit = 0.
For each price, update min_price = min(min_price, price).
Update answer = max(answer, price - min_price).

Naive Solution — Brute Force

Try all possible buy/sell day pairs.

Python

class Solution:
    def maxProfit(self, prices):
        answer = 0

        for i in range(len(prices)):
            for j in range(i + 1, len(prices)):
                answer = max(
                    answer,
                    prices[j] - prices[i]
                )

        return answer

C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int answer = 0;
        for (int i = 0; i < prices.size(); i++)
            for (int j = i + 1; j < prices.size(); j++)
                answer = max(answer, prices[j] - prices[i]);
        return answer;
    }
};

Java

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

JavaScript

var maxProfit = function(prices) {
    let answer = 0;
    for (let i = 0; i < prices.length; i++)
        for (let j = i + 1; j < prices.length; j++)
            answer = Math.max(answer, prices[j] - prices[i]);
    return answer;
};

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

Optimized Code (Python 3)

Python

class Solution:
    def maxProfit(self, prices):
        min_price = float("inf")
        answer = 0

        for price in prices:
            min_price = min(
                min_price,
                price
            )

            answer = max(
                answer,
                price - min_price
            )

        return answer

C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int answer = 0;
        for (int price : prices) {
            minPrice = min(minPrice, price);
            answer = max(answer, price - minPrice);
        }
        return answer;
    }
};

Java

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

JavaScript

var maxProfit = function(prices) {
    let minPrice = Infinity;
    let answer = 0;
    for (const price of prices) {
        minPrice = Math.min(minPrice, price);
        answer = Math.max(answer, price - minPrice);
    }
    return answer;
};

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

Takeaway

Pattern — Maintain minimum left value while scanning once