Best Time to Buy and Sell Stock (LC 121)

Pattern: Greedy / One-pass tracking of minimum
Difficulty: Easy
Key Concept: Track the lowest price seen so far; the best profit ending on each day is price today - min price so far.

Problem Statement

You are given an array prices where prices[i] is the price of a stock on day i. You may complete at most one transaction: buy one share on one day and sell it on a later day. Return the maximum profit you can achieve. If no profit is possible, return 0.

Input: Integer array prices (length ≥ 1).
Output: Non-negative integer — maximum (sell price - buy price) with buy before sell, or 0.

---

1. Algorithm & Pseudocode

Brute force (all pairs)

1. Initialize maxProfit = 0.
2. For each buy from 0 to n - 2:
   • For each sell from buy + 1 to n - 1:
     • profit = prices[sell] - prices[buy]
     • maxProfit = max(maxProfit, profit)
3. Return maxProfit.

Optimal (one pass)

1. Initialize minPrice = +∞ (in code: Integer.MAX_VALUE) and maxProfit = 0.
2. For each price in prices (in order):
   • maxProfit = max(maxProfit, price - minPrice)
   • minPrice = min(minPrice, price)
3. Return maxProfit.

Order of updates: For each day’s price, compute profit using the smallest price seen on earlier days only. So for each price, update maxProfit first (treating minPrice as “best buy so far from the past”), then fold price into minPrice for future days. That matches “best profit if I sell today” = today’s price − cheapest prior day.

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Why brute force works: Every valid trade is some pair (buy, sell) with buy < sell. Checking all pairs covers the optimum — but there are O(n²) pairs.
• Why we only need the minimum so far: If you sell on day i, you want the cheapest buy among days 0 .. i-1. You do not need to remember every earlier price, only the smallest one.
• Why start maxProfit at 0: If prices only go down, the best “profit” is not selling (or equivalently no positive gain), so the answer is 0.
• Integer.MAX_VALUE and the first day: Initialize minPrice to Integer.MAX_VALUE. On the first iteration, price - minPrice wraps in 32-bit arithmetic to a negative value, so Math.max(maxProfit, …) leaves maxProfit at 0. Then minPrice becomes the first real price. (If the first price were Integer.MAX_VALUE, you would still be safe for typical stock-price inputs.)
• Math.max / Math.min: Keep the rolling best profit and the rolling minimum buy price without extra branches.
• Autoboxing: Use primitive int for minPrice and maxProfit. Using Integer in hot loops adds boxing cost and can invite NullPointerException if a reference were ever null; stick to int.

---

3. The Dry Run

prices = [7, 1, 5, 3, 6, 4]

Step	price	minPrice (before profit)	price - minPrice	maxProfit (after)	minPrice (after)
init	—	MAX	—	0	MAX
1	7	MAX	negative (wrapped)	0	7
2	1	7	-6	0	1
3	5	1	4	4	1
4	3	1	2	4	1
5	6	1	5	5	1
6	4	1	3	5	1

Answer: 5 (buy at 1, sell at 6).

---

4. Java Solution

Brute Force

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

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

Optimal

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;
}

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

---

5. The “Java vs. Others” Edge

• Integer.MAX_VALUE plays the same role as INT_MAX from <climits> in C++ for initializing a “minimum so far” sentinel.
• Math.max / Math.min work on int without importing extra libraries (unlike some languages that need a helper namespace).
• Autoboxing pitfall: Declaring Integer minPrice = Integer.MAX_VALUE and mixing with int works but adds boxing cost and can invite NullPointerException if something sets it to null. Prefer plain int for competitive-style solutions.
• Integer overflow: Profit calculation stays within typical problem constraints, but in general subtracting two large int prices could overflow; long would be safer for extreme inputs (not required for standard LC 121).

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n²)	O(1)	All buy/sell pairs.
Optimal	O(n)	O(1)	Single pass; track min price and best profit.