121. Best Time to Buy and Sell Stock

This is the problem that teaches one of the most reusable tricks in easy and medium interviews: replace an inner loop with one running variable. Here it collapses an $O(n^2)$ scan into a single $O(n)$ pass.

Question

You are given an array prices where prices[i] is the price of a given stock on the i-th day.

• You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
• Return themaximum profityou can achieve from this transaction.
• If you cannot achieve any profit, return 0.
• Example1

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation:
Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

• Example2

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

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

Algorithm

• Kadane’s Algorithm (Maximum Subarray Sum)
  • TC: $O(n)$
  • SC: $O(1)$
• Dynamic Programming
  • TC: $O(n)$
  • SC: $O(n)$

Answer

/**
 * Kadane's Algorithm
 * TC: O(n)
 * SC: O(1)
 */
public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }

    int maxProfit = 0;
    // min sell price
    int minPrice = prices[0];

    // buy before sell order is guaranteed
    for (int i = 1; i < prices.length; i++) {
        // profit = current price (sell) - minimum buy price
        int profit = prices[i] - minPrice;

        // maximum profit
        maxProfit = Math.max(maxProfit, profit);

        // track the cheapest buy price seen so far
        minPrice = Math.min(minPrice, prices[i]);
    }
    return maxProfit;
}

/**
 * Dynamic Programming
 * dp[i] = maximum profit achievable up to day i
 * TC: O(n)
 * SC: O(n)
 */
public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }

    int n = prices.length;
    int[] dp = new int[n]; // dp[i] = max profit up to day i
    dp[0] = 0;
    int minPrice = prices[0];

    for (int i = 1; i < n; i++) {
        // profit if sold on day i vs max profit up to day i-1
        dp[i] = Math.max(dp[i - 1], prices[i] - minPrice);
        minPrice = Math.min(minPrice, prices[i]);
    }

    return dp[n - 1];
}

Explain

Brute Force → 1-pass

Brute Force fixes the buy day and searches all sell days after it.

// Brute Force: fix buy day, search sell days
for (int i = 0; i < prices.length; i++) {       // buy day (fixed)
    for (int j = i+1; j < prices.length; j++) { // sell day (search)
        maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
    }
}

To compress into 1-pass, flip the perspective — fix the sell day and search previous buy days.

// Flipped: fix sell day, search buy days
for (int j = 1; j < prices.length; j++) {       // sell day (fixed)
    for (int i = 0; i < j; i++) {               // buy day (search)
        maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
    }
}

When sell day j is fixed, prices[j] - prices[i] is maximized when prices[i] is the smallest value seen so far. No need to try every buy day — only the minimum matters.

// prices[j] - min(prices[0] ~ prices[j-1])
// → replace inner loop with a single minPrice variable
for (int j = 1; j < prices.length; j++) {       // sell day
    maxProfit = Math.max(maxProfit, prices[j] - minPrice);
    minPrice = Math.min(minPrice, prices[j]);
}

Key Insight

By flipping the perspective to the sell day, the entire inner loop is just “find the previous minimum price.”
Replacing it with a single minPrice variable reduces O(n²) → O(n).

Two edge cases fall out for free. A strictly falling series like [7,6,4,3,1] never produces a positive profit, so maxProfit stays 0. And a single day can’t complete a buy-then-sell, which the length guard catches up front. If this feels familiar, it should: it’s Kadane’s algorithm wearing a different hat — instead of the largest running sum, you track the largest running gap above the cheapest price seen so far.

---

Greedy / Kadane’s / 1-pass — What’s the difference?

They are all valid descriptions of the same code — just different perspectives.

Perspective	Description
Greedy	At each step, greedily keep track of the best (lowest) buy price seen so far
Kadane’s	DP recurrence compressed into a single variable (space optimization)
1-pass	Implementation style — the array is traversed exactly once

References

• https://leetcode.com/problems/best-time-to-buy-and-sell-stock/