Best Time to Buy and Sell Stock - One-Pass Strategy

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Key Takeaways

📋 Problem Statement

You may complete at most one transaction: choose one day to buy and a later day to sell. If no profit is possible, return 0.

Examples

Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Buy at 1 (day 2), sell at 6 (day 5)

Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Prices only decrease, so no profitable sale exists

Constraints

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

🎯 Real-World Analogy

Farmers Market Decision Rule

You visit a market once per day. You can buy produce once and sell it once later. Your decision quality depends on remembering the cheapest price seen so far, then checking whether today offers a better resale margin.

You do not need future prediction. You only need two pieces of state while moving left to right: the minimum historical price and the best profit found so far.

💡 Key Insights

The sell day must be after the buy day, so process in time order.
For each day, best possible profit today is price - min_price_so_far.
Update min_price_so_far before considering future days.
Track running maximum profit; initialize to 0 for no-profit cases.
This pattern is a one-pass min/max streaming optimization.

💻 Solution Approaches

Approach 1: Brute Force Pair Scan

Time: O(N²) | Space: O(1)

Try every buy day with every later sell day. Correct but too slow for large arrays.

Approach 2: One-Pass Min Tracker (Recommended)

Time: O(N) | Space: O(1)

Track the lowest price seen and compute candidate profit at each step.

Python Implementation

          from typing import List


def max_profit(prices: List[int]) -> int:
    """
    Return max profit from one buy/sell transaction.

    Time: O(N)
    Space: O(1)
    """
    min_price = float("inf")
    best = 0

    for price in prices:
        if price < min_price:
            min_price = price
        else:
            best = max(best, price - min_price)

    return best
        

JavaScript Implementation

          function maxProfit(prices) {
  /**
   * Return max profit from one buy/sell transaction.
   *
   * Time: O(N)
   * Space: O(1)
   */
  let minPrice = Number.POSITIVE_INFINITY;
  let best = 0;

  for (const price of prices) {
    if (price < minPrice) {
      minPrice = price;
    } else {
      best = Math.max(best, price - minPrice);
    }
  }

  return best;
}
        

🔍 Step-by-Step Walkthrough

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

Start: min_price = inf, best = 0

            Day 1, price 7: min_price = 7, best = 0
          
            Day 2, price 1: min_price = 1, best = 0
          
            Day 3, price 5: profit = 5 - 1 = 4, best = 4
          
            Day 4, price 3: profit = 3 - 1 = 2, best stays 4
          
            Day 5, price 6: profit = 6 - 1 = 5, best = 5
          
            Day 6, price 4: profit = 4 - 1 = 3, final best = 5

⚡ Complexity Analysis

Time Complexity: O(N)

We iterate over the list once and do O(1) work per day.

Space Complexity: O(1)

Only two scalar variables are maintained regardless of input size.

🔧 Edge Cases

Strictly decreasing prices: result must be 0
Single-element array: cannot sell after buy, result 0
Flat prices: no positive spread, result 0
Best buy appears before best sell by large gap
Multiple local peaks; algorithm must preserve global best

🧪 Test Cases

Python

          def test_max_profit():
    assert max_profit([7, 1, 5, 3, 6, 4]) == 5
    assert max_profit([7, 6, 4, 3, 1]) == 0
    assert max_profit([2, 4, 1]) == 2
    assert max_profit([1]) == 0
    assert max_profit([3, 3, 3]) == 0
    assert max_profit([2, 1, 2, 1, 0, 1, 2]) == 2

    print("✅ all tests passed")
        

JavaScript

          function testMaxProfit() {
  console.assert(maxProfit([7, 1, 5, 3, 6, 4]) === 5, "test 1");
  console.assert(maxProfit([7, 6, 4, 3, 1]) === 0, "test 2");
  console.assert(maxProfit([2, 4, 1]) === 2, "test 3");
  console.assert(maxProfit([1]) === 0, "test 4");
  console.assert(maxProfit([3, 3, 3]) === 0, "test 5");
  console.assert(maxProfit([2, 1, 2, 1, 0, 1, 2]) === 2, "test 6");

  console.log("✅ all tests passed");
}
        

💼 Interview Tips

State constraint explicitly: sell must happen after buy.
Explain why tracking only minimum historical price is sufficient.
Clarify why no-profit arrays return 0 and not negative values.
Compare to Kadane-style rolling optimizations (streaming state).
Mention follow-up variant: multiple transactions requires different logic.

🎓 Key Takeaways

One-pass min tracking converts an O(N²) pair search into O(N).
This is a strong interview pattern: maintain best historical state while scanning.
When constraints enforce order, think in streaming terms instead of pair combinations.

← Back to All Algorithms