01: Introduction
They think “check all pairs” is fine. For 10 elements it is. For 100,000 elements? Your solution will time out. This problem rewards clear algorithmic thinking.
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.
The optimal strategy in one transaction is to hold the stock from its historical minimum to the highest point after that minimum. The algorithm essentially simulates this automatically.
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.
defmax_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_profitWith n = 100,000, this runs ~5 billion comparisons. Even at 10⁹ operations per second, that’s 5 seconds. LeetCode will time out. You need O(n).
05: 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.
For any selling day j, the best buying day is always the day with the minimum price before j. So we just track that minimum as we go.
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 don’t we 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: Flowchart
08 Python Solution
defmax_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 |
Buy on Day 1 (price = 1), Sell on Day 4 (price = 6). Maximum Profit = 5.
10: Price Visualization
Sell point (max profit)
Other days
11: Time & Space Complexity
O(n)
Time Complexity
We scan the array exactly once. Every element is visited one time.
O(1)
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 (Best Time to Buy and Sell Stock)
Can you solve this in O(n) time and O(1) space?
What happens if the array has only one element?
What if all prices are decreasing — what should you return?
How would you extend this if two transactions were allowed? (LeetCode 123)
Why can’t you sell before you buy in this problem?
Why do you initialize
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.
This problem teaches you the power of single-pass greedy thinking — a pattern that appears in dozens of other DSA problems. Master this and the rest becomes easier.
16: Frequently Asked Questions(Best Time to Buy and Sell Stock)
max - min can give you an invalid trade where you’d need to go back in time.if you want more follow
if you more on programming follow
if you want to see this in a good stylish way click this best-time-buy-sell-stock