Best Time to Buy and Sell Stock (LC 121)

Pattern: Single-Pass Min Tracker / Greedy Difficulty: Easy Key Concept: Track the minimum price seen so far while walking forward; the best profit at index i is prices[i] - minSoFar.

Problem Statement

You are given an array prices where prices[i] is the price of a stock on day i. You may buy on one day and sell on a later day. Return the maximum profit achievable. If no profit is possible, return 0.

Input

• prices — integer array (length ≥ 1)

Output

• int — max profit

Example

• prices = [7, 1, 5, 3, 6, 4] → 5 (buy on day 2 at 1, sell on day 5 at 6)
• prices = [7, 6, 4, 3, 1] → 0

---

1. Algorithm & Pseudocode

Brute force

1. For each i from 0 to n-1:
2. For each j from i+1 to n-1:
3. Track max(profit, prices[j] - prices[i]).

Optimal

1. Let minPrice = Integer.MAX_VALUE, maxProfit = 0.
2. For each price in prices:
3. If price < minPrice, update minPrice.
4. Else compute price - minPrice and update maxProfit if larger.
5. Return maxProfit.

---

2. Step-by-Step Analysis

Why brute force is correct You consider every (buy, sell) pair, so the optimum is reached.

Why brute force is slow (O(n^2)) — too slow for n up to 10^5.

Why the single pass works At day i, the best buy price is fixed — it’s the minimum price seen on days 0..i-1 (and today, since buying and selling same day yields 0 profit). So you only need to remember one number as you scan: minPrice so far. The best profit ending at day i is prices[i] - minPrice. The overall answer is the maximum of these.

Why we don’t need a “best buy day” We only need the best profit value, not the days, so tracking the min value is enough.

ASCII Trace

prices: [7, 1, 5, 3, 6, 4]
i=0  price=7 minPrice=7 profit=0
i=1  price=1 minPrice=1 profit=0
i=2  price=5 minPrice=1 profit=4
i=3  price=3 minPrice=1 profit=4
i=4  price=6 minPrice=1 profit=5  ← answer
i=5  price=4 minPrice=1 profit=5

---

3. The Dry Run

Step	price	minPrice (before)	Action	maxProfit
1	7	INT_MAX	7 < MAX → minPrice = 7	0
2	1	7	1 < 7 → minPrice = 1	0
3	5	1	5-1 = 4 > 0 → maxProfit = 4	4
4	3	1	3-1 = 2 < 4 → no change	4
5	6	1	6-1 = 5 > 4 → maxProfit = 5	5
6	4	1	4-1 = 3 < 5 → no change	5

Return 5.

---

4. Java Solution

Brute Force

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

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

Optimal

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

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

---

5. The “Java vs. Others” Edge

• Integer.MAX_VALUE as sentinel — never overflows because price is bounded by 10^4 per LC constraints.
• Use enhanced for-loop over indexed loop when you don’t need the index — clearer intent.
• Could combine the if/else into maxProfit = Math.max(maxProfit, price - minPrice); minPrice = Math.min(minPrice, price); — but the if/else is slightly faster because it avoids Math.max when a new min is found.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	(O(n^2))	(O(1))	Try every pair.
Optimal	(O(n))	(O(1))	Single pass, two trackers.