ToolMight LogoToolMight
EasySliding WindowPattern: One-Pass Running MinimumPattern: Greedy

Best Time to Buy and Sell Stock

Determine the maximum single-transaction profit from daily stock prices. A classic demonstration of how tracking a running minimum transforms an O(n²) pair search into an O(n) single pass.

Problem Statement

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 the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Examples & Constraints

Example 1
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.
Example 2
Input: prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: In this case, prices continually decrease, no profitable transactions are possible and max profit = 0.
Constraints
  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

One-Pass Running Minimum (Greedy)

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

Track the lowest price seen so far as you iterate through time, evaluating potential profit at each day.

Time ComplexityO(n)

We make a single pass through the array of length N.

Space ComplexityO(1)

Only two scalar variables (minPrice, maxProfit) are maintained.

Underlying algorithmic logic

The Core Mental Model: You Cannot Time Travel

In financial markets, time strictly moves forward. You cannot buy tomorrow and sell yesterday.

If you make the decision to sell your share on Day `i`, what was the ideal day to have bought it?
Simply: the day with the lowest price that occurred before Day `i`.

The Greedy Single-Pass Strategy

Rather than comparing every possible pair of buy and sell days in O(n²) time:

  1. Maintain two numbers in memory:
  • minPrice: the lowest price observed up to today (initialized to infinity).
  • maxProfit: the greatest profit achieved so far (initialized to 0).
  1. For each day's price:
  • If price < minPrice, we've found a new record-low purchase price! Update minPrice = price.
  • Otherwise, if we sold today, our profit would be price - minPrice. If this beats our record, update maxProfit = price - minPrice.
  1. Return maxProfit.

This tracks optimal historical state in a single O(n) scan using pure O(1) memory.

Step-by-step execution walkthrough

1
Day 1 (Price 7)

minPrice becomes 7, maxProfit = 0.

minPrice = 7, maxProfit = 0
2
Day 2 (Price 1)

Price 1 is lower than minPrice (7). Update minPrice = 1.

minPrice = 1, maxProfit = 0
3
Day 3 (Price 5)

Profit = 5 - 1 = 4. Update maxProfit = 4.

minPrice = 1, maxProfit = 4
4
Day 5 (Price 6)

Profit = 6 - 1 = 5. Update maxProfit = 5.

minPrice = 1, maxProfit = 5
Advantages
  • •Optimal O(n) runtime
  • •Constant O(1) space
  • •Extremely clean implementation
Trade-offs
  • •Only solves the single-transaction variant

Code Implementations

Copy & paste production-ready solutions for One-Pass Running Minimum (Greedy) in your language of choice

File: solution.py
Python
def max_profit(prices: list[int]) -> int:
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
    return max_profit
if __name__ == "__main__":
    prices = [7, 1, 5, 3, 6, 4]
    print(f"Max Profit: {max_profit(prices)}")
Interactive visualizer available

Understand Sliding Window Visually

Track contiguous subarrays of a larger array using start/end boundary pointers to avoid redundant recalculations. Test live edge cases and watch memory state transitions step-by-step.

Launch Sliding Window Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
EasyBinary Search
Visualizer

Binary Search

Locate a target value in a sorted array in O(log n) logarithmic time. Like opening a dictionary in the middle, each comparison eliminates half the remaining items.

2 approaches(O(log n))
Learn logic
MediumDynamic Programming
Visualizer

Maximum Subarray (Kadane's Algorithm)

Find the contiguous slice of an array that yields the largest sum. Kadane's algorithm demonstrates the art of shedding negative historical baggage in O(n) linear time.

1 approach(O(n))
Learn logic