ToolMight Logo
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 Memory Simulator

Struggling to visualize how Sliding Window operates?

Watch pointers move, arrays shift, and recursion stacks unwind in real time. Step through custom inputs before writing code.

Launch Sliding Window Visualizer

Frequently Asked Questions

Practice Similar Algorithmic Patterns

Browse all 31 problems