Best Time to Buy and Sell Stock — O(n) Python Solution Explained
To maximize profit from a single stock transaction, scan prices once. Track the minimum price seen so far and at every step compute current price − min price. Update the max profit if this value is higher. This runs in O(n) time and O(1) space.
01 Introduction
Imagine you could see Apple's stock prices for the past week — $180, $140, $155, $130, $170, $160. You can buy once and sell once. Which days do you pick to make the most money?
This is the Best Time to Buy and Sell Stock problem — one of the most commonly asked questions in coding interviews at Google, Amazon, Microsoft, and every major tech company. It looks simple on the surface, but beginners keep getting it wrong because they jump straight to checking every possible pair of days.
In this guide you'll understand exactly why the naive approach fails, how the optimal single-pass approach works, and how to explain it confidently in any interview.
02 Problem Statement
You are given an array prices where prices[i] is the price of a stock on day i. You want to maximize your profit by choosing one day to buy and a later day to sell. Return the maximum profit possible. If no profit is possible, return 0.
Example 1
# Input
prices = [7, 1, 5, 3, 6, 4]
# Output
5
# Explanation: Buy on day 2 (price=1), sell on day 5 (price=6). Profit = 6-1 = 5Example 2
# Input
prices = [7, 6, 4, 3, 1]
# Output
0
# Explanation: Prices only go down. No transaction is beneficial.Input / Output Format
| Field | Type | Description |
|---|---|---|
| prices | List[int] | Stock prices for each day |
| Output | int | Maximum profit (0 if no profit) |
Constraints
1 ≤ prices.length ≤ 10⁵0 ≤ prices[i] ≤ 10⁴- You must buy before you sell (not on the same day)
- Only one transaction allowed
03 Real World Explanation
Think about how stock traders actually think. Their core goal is to buy low, sell high. But the catch is timing — you can only sell after you buy, not before.
Here's where beginners get confused in real trading too: they see a high price on day 3 and a low price on day 5. They think "sell on day 3, buy on day 5." That's short-selling, which is a completely different concept. In this problem, you always buy first, sell second.
This same logic applies to cryptocurrency trading — finding the right entry point is everything. If you bought Bitcoin at $15,000 and sold at $60,000, your profit is $45,000. This algorithm would find that exact pair automatically.
04 Naive Approach — Brute Force O(n²)
The first idea most beginners have: for every possible buying day, check every possible selling day after it. Track the pair that gives maximum profit.
def max_profit_brute(prices):
n = len(prices)
max_profit = 0
for i in range(n): # buy day
for j in range(i+1, n): # sell day (must be after buy)
profit = prices[j] - prices[i]
max_profit = max(max_profit, profit)
return max_profit05 Optimal Approach — Single Pass O(n)
The insight is elegant. You don't need to check every pair. You just need two variables as you scan left to right:
- min_price — the lowest price seen so far (best time to have bought)
- max_profit — the highest profit achievable so far
For each price: if it's lower than min_price, update min_price. Otherwise, see if selling now beats your current best profit.
06 Key Intuition
Why does tracking the minimum work? Because profit = sell_price − buy_price. To maximize profit for a fixed sell day, you want the smallest possible buy price — and that's always the minimum price seen so far.
Common Misunderstanding
Some students think: "What if I update min_price but then I miss a higher profit?" That can't happen — because when you update min_price to a new low, you're making future profits potentially bigger, not smaller. A lower buy price can only help.
Why we don't reset max_profit when updating min_price
Because max_profit already holds the best answer we've seen so far. We're just potentially improving future profits. The overall maximum is preserved.
07 Algorithm Flowchart
Update max_profit if profit > max_profit
08 Python Solution
def max_profit(prices):
"""
Find maximum profit from a single buy-sell transaction.
Args:
prices: List of stock prices indexed by day
Returns:
Maximum achievable profit (0 if no profit possible)
"""
if not prices or len(prices) < 2:
return 0
min_price = float('inf') # Start with infinity (any price beats this)
max_profit = 0 # At worst, we make zero (don't trade)
for price in prices:
if price < min_price:
min_price = price # Found a cheaper buying point
else:
profit = price - min_price # What if we sell today?
max_profit = max(max_profit, profit) # Keep the best
return max_profit
# --- Input Handling ---
if __name__ == "__main__":
n = int(input("Number of days: "))
prices = list(map(int, input("Prices (space-separated): ").split()))
print(f"Maximum Profit: {max_profit(prices)}")09 Dry Run — Step by Step
Input: [7, 1, 5, 3, 6, 4]
| Day | Price | min_price | Current Profit | max_profit | Action |
|---|---|---|---|---|---|
| 0 | 7 | 7 | — | 0 | Set min = 7 |
| 1 | 1 | 1 | — | 0 | New min found (1 < 7) |
| 2 | 5 | 1 | 5−1 = 4 | 4 | Profit updated |
| 3 | 3 | 1 | 3−1 = 2 | 4 | No improvement |
| 4 | 6 | 1 | 6−1 = 5 | 5 | Best profit! ✓ |
| 5 | 4 | 1 | 4−1 = 3 | 5 | No improvement |
10 Price Visualization
11 Time & Space Complexity
Time Complexity
We scan the array exactly once. Every element is visited one time.
Space Complexity
Only two variables used — min_price and max_profit. No extra arrays.
| Approach | Time | Space | Verdict |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Too slow for large input |
| Single Pass (Optimal) | O(n) | O(1) | Interview-ready ✓ |
12 Test Cases
13 Common Interview Questions
min_price to infinity instead of prices[0]?
14 Mistakes Beginners Make
Selling before buying
Forgetting that sell index must be greater than buy index. Always move left-to-right.
Returning negative profit
If no profit is possible, return 0, not a negative number. Initialize max_profit = 0, not -infinity.
Not updating min_price correctly
Some students only check profit and never update min_price when they find a lower value. This breaks the entire logic.
Using max of array minus min of array
This looks smart but it's wrong. The minimum might come after the maximum — meaning you'd have to sell before buying. Always ensure min appears before max in time.
15 Conclusion
The Best Time to Buy and Sell Stock problem is a perfect example of how simple thinking leads to elegant solutions. Instead of brute-forcing all pairs in O(n²), you ask one smarter question at each step: "If I sell today, what's the best price I could have bought at?"
Track the historical minimum, compute the current profit, update the answer. That's it. Two variables, one loop, O(n) time, O(1) space.
16 Frequently Asked Questions
max - min can give you an invalid trade where you'd need to go back in time.