3.14 Best Time to Buy and Sell Stock

3.14.1 Problem Metadata

3.14.2 Description

Given prices where prices[i] is the stock price on day i, find the maximum profit from a single buy and sell transaction.

3.14.3 Examples

Input: [7,1,5,3,6,4]
Output: 5

3.14.4 Constraints

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

3.14.5 Solution - Track Min Price

3.14.5.1 Walkthrough

This solution uses a single-pass MinMax approach to find the maximum profit from a single buy-sell transaction.

Core Strategy:

The key insight is that to maximize profit, we need to: 1. Buy at the lowest price encountered so far 2. Sell at a price that gives maximum profit relative to that minimum

This is achieved by tracking two values as we scan left to right: - minPrice: The minimum price seen so far (best buying opportunity) - maxProfit: The maximum profit achievable (best selling opportunity after buying at minPrice)

Key Insight: Why Single Pass Works

For any selling day i, the optimal buying day must be before day i and at the minimum price among all previous days. We don’t need to look ahead because: - We can only buy before we sell - Buying at a lower price always yields better profit for the same selling price

At each day, we ask two questions: 1. “If I sold today, what’s my profit?” → price - minPrice 2. “Is today’s price a new minimum?” → Update minPrice if needed

Visual Example Walkthrough:

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

Day 0: price=7
  minPrice = min(∞, 7) = 7
  maxProfit = max(0, 7-7) = 0
  (Can't make profit on first day)

Day 1: price=1
  minPrice = min(7, 1) = 1 ✓ NEW MIN (best time to buy!)
  maxProfit = max(0, 1-1) = 0
  (Updated buy price, no profit yet)

Day 2: price=5
  minPrice = min(1, 5) = 1
  maxProfit = max(0, 5-1) = 4 ✓ NEW MAX
  (Selling at 5 after buying at 1 gives profit 4)

Day 3: price=3
  minPrice = min(1, 3) = 1
  maxProfit = max(4, 3-1) = 4
  (Profit of 2 is worse than existing 4)

Day 4: price=6
  minPrice = min(1, 6) = 1
  maxProfit = max(4, 6-1) = 5 ✓ NEW MAX
  (Selling at 6 after buying at 1 gives profit 5)

Day 5: price=4
  minPrice = min(1, 4) = 1
  maxProfit = max(5, 4-1) = 5
  (Profit of 3 is worse than existing 5)

Result: 5 (Buy at day 1 price=1, sell at day 4 price=6)

Why This MinMax Strategy Works:

  • We maintain the global minimum price seen so far
  • For each price, we compute potential profit assuming we bought at that minimum
  • We keep the global maximum profit across all days
  • This guarantees we find the optimal buy-sell pair because:
    • Any valid sell day has been compared against the best possible buy day (minimum price before it)
    • We explore all possible selling points in one pass

3.14.5.2 Analysis

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

3.14.5.3 Implementation Steps

  1. Initialize minPrice = Integer.MAX_VALUE, maxProfit = 0.
  2. For each price p:
    • maxProfit = max(maxProfit, p - minPrice).
    • minPrice = min(minPrice, p).
  3. Return maxProfit.

3.14.5.4 Code - Java

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;

    for (int price : prices) {
        minPrice = Math.min(minPrice, price);
        maxProfit = Math.max(maxProfit, price - minPrice);
    }

    return maxProfit;
}