Skip to content

121. Best Time to Buy and Sell Stock

Question

Given an array prices where prices[i] is the price of a stock on day \(i\), find the maximum profit achievable by doing exactly one transaction (buy on day \(i\), sell on day \(j\), where \(i < j\)). Return 0 if no profit can be made.

Solution

Pattern

State Tracking (Greedy / 1D DP) Iterate through the timeline keeping track of the historical minimum. At each step, calculate the profit if you were to sell today, and update the global maximum profit.

How to Identify

  • The problem asks to maximize a difference between two elements in an array: \(prices[j] - prices[i]\).
  • There is a strict temporal/index constraint: \(i < j\) (buy before you sell).
  • The solution requires evaluating historical data against current data, signaling state compression.

Description

Step-by-step explanation:

  1. Validate the input. If the array has fewer than 2 elements, no transaction is possible, return 0.
  2. Initialize min_price to the first day's price. This represents the cheapest day we could have bought the stock so far.
  3. Initialize max_profit to 0.
  4. Iterate through the array starting from the second day.
  5. For each day, calculate the potential profit if we sold today: current_price - min_price.
  6. Update max_profit if this potential profit is greater than our recorded max_profit.
  7. Update min_price if the current_price is lower than the historical min_price. (This cheaper price will be used for future days).
  8. Return max_profit.

The Intuition

Think of this as "hindsight is 20/20." If you are forced to sell your stock today, what is the absolute best profit you could make? To maximize today's profit, you logically must have bought the stock at the absolute lowest price available on all days prior to today. By maintaining a running record of the lowest price seen so far (min_price), you can instantly calculate the best possible profit for any given day in \(O(1)\) time.

Complexity

Label Worst Average
Time Complexity \(O(N)\) \(O(N)\)
Space Complexity \(O(1)\) \(O(1)\)

Time Complexity

We iterate through the array of size \(N\) exactly once. At each step, we perform constant-time operations (two assignments/comparisons). Thus, time complexity is \(O(N)\).

Space Complexity

We only maintain two integer variables (min_price and max_profit) regardless of the size of the input array. Auxiliary space is strictly \(O(1)\).

Code

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0; 
        }

        int minPrice = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            int currentProfit = prices[i] - minPrice;

            if (currentProfit > maxProfit) {
                maxProfit = currentProfit;
            }

            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
        }

        return maxProfit;
    }
}

Caveats

  • Shorting Stock: This algorithm implicitly assumes you can only go "long" (buy first, sell later). If the problem allows short-selling (sell first, buy later to cover), the logic fundamentally changes.
  • Reverse Iteration: Iterating backward (tracking max_price_in_future) works mathematically for static arrays, but fails catastrophically if applied to live data streams where future prices are unknown.

Concepts to Think About

  • DP State Compression: This is essentially a space-optimized Dynamic Programming solution. The unoptimized DP relation is \(DP[i] = \max(DP[i-1], prices[i] - \min(prices[0...i]))\). Because we only need the minimum of the prefix, we compress the \(O(N)\) prefix-minimum array into a single \(O(1)\) variable.
  • Streaming Algorithms: Algorithms that process data in a single forward pass with \(O(1)\) space are highly scalable for streaming data (e.g., processing terabytes of financial tick data in real-time).
  • Prefix Minimums: This problem introduces the concept of carrying a "prefix state" (the minimum of all elements seen so far) which is a foundational pattern for many array problems.

Logical Follow-up

Question: What if you could execute as many transactions as you like (buy and sell multiple times), but you can only hold at most one share at a time? (Best Time to Buy and Sell Stock II) Solution: You use a Greedy approach. Since you know the future, you capture every single upward price movement. Iterate through the array. Anytime \(prices[i] > prices[i-1]\), add the difference \((prices[i] - prices[i-1])\) to your total profit. This effectively captures the exact sum of all ascending slopes on the price graph in \(O(N)\) time and \(O(1)\) space.

Question: What if you can make at most 2 transactions? (Best Time to Buy and Sell Stock III) Solution: You must use Dynamic Programming. You track four states at every step: the minimum price after the first buy (buy1), the max profit after the first sell (sell1), the minimum effective price after the second buy (buy2 = prices[i] - sell1), and the max profit after the second sell (sell2). This is solved in \(O(N)\) time and \(O(1)\) space using state machines.

Question: What if there is a cooldown period of 1 day after you sell before you can buy again? Solution: We use a State Machine Dynamic Programming approach. We maintain three states for each day: held (we own a stock), sold (we sold today, triggering a cooldown tomorrow), and reset (we are resting or waiting to buy). The transitions between these states map out the optimal path in \(O(N)\) time.

Comments