Best Time to Buy and Sell Stock — O(n) Greedy Explained [Amazon Favorite]

Problem Statement

You are given an array prices where prices[i] is the price of a stock on day i. You want to maximize your profit by choosing one day to buy and a different day in the future to sell. Return the maximum profit. If no profit is possible, return 0.

Example 1:

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5
Reason: Buy on day 2 (price=1), sell on day 5 (price=6), profit = 6-1 = 5

Example 2:

Input:  prices = [7, 6, 4, 3, 1]
Output: 0
Reason: Prices only decrease — no profitable transaction possible

Intuition
Solutions in All 5 Languages
C
C++
Java
JavaScript
Python
Complexity Analysis
The Stock Problem Family (FAANG loves these)
Edge Cases
Key Takeaway

Intuition

We want to find max(prices[j] - prices[i]) where j > i.

Key insight: Instead of checking all pairs (O(n²)), track the minimum price seen so far as we scan left to right. For each day, the best profit IF we sell today is prices[i] - minSoFar.

minSoFar = prices[0]
maxProfit = 0

for each price:
    maxProfit = max(maxProfit, price - minSoFar)
    minSoFar  = min(minSoFar, price)

Think of it as: "What's the cheapest I could have bought before today? If I sell today, what's my profit?"

Solutions in All 5 Languages

C

#include <stdio.h>

int maxProfit(int* prices, int pricesSize) {
    if (pricesSize == 0) return 0;
    
    int minPrice = prices[0];
    int maxProfit = 0;
    
    for (int i = 1; i < pricesSize; i++) {
        int profit = prices[i] - minPrice;
        if (profit > maxProfit) maxProfit = profit;
        if (prices[i] < minPrice) minPrice = prices[i];
    }
    
    return maxProfit;
}

int main() {
    int prices[] = {7, 1, 5, 3, 6, 4};
    printf("%d\n", maxProfit(prices, 6)); // 5
    return 0;
}

C++

#include <vector>
#include <algorithm>
using namespace std;

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

Java

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

JavaScript

/**
 * @param {number[]} prices
 * @return {number}
 */
function maxProfit(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;
    
    for (const price of prices) {
        maxProfit = Math.max(maxProfit, price - minPrice);
        minPrice  = Math.min(minPrice, price);
    }
    
    return maxProfit;
}

Python

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        
        for price in prices:
            max_profit = max(max_profit, price - min_price)
            min_price  = min(min_price, price)
        
        return max_profit

Complexity Analysis

	Time	Space
Optimal	O(n)	O(1)

Single pass through the array, constant extra variables.

The Stock Problem Family (FAANG loves these)

Variant	Transactions	Trick
Stock I (this)	1	Min so far
Stock II	Unlimited	Sum all gains
Stock III	2	4 states DP
Stock IV	K	DP k states
Stock Cooldown	Unlimited, 1-day gap	3 states
Stock with Fee	Unlimited, fee per tx	2 states

Stock II (unlimited transactions) — just sum every positive gap:

def maxProfitII(prices):
    return sum(max(0, prices[i] - prices[i-1]) for i in range(1, len(prices)))

Edge Cases

prices = [1]          → 0  (only one day, can't sell)
prices = [2, 1]       → 0  (only decreasing)
prices = [1, 2]       → 1  (buy day 1, sell day 2)
prices = []           → 0  (empty array)

Key Takeaway

The "track minimum/maximum seen so far" pattern is foundational for:

Best time to buy stock variants
Maximum profit in job scheduling
Minimum cost path problems

Next: Problem 3 — Contains Duplicate →