121 - Best Time to Buy and Sell Stock

Difficulty: Easy | Pattern: Greedy / One-Pass Scan | Company tags: Amazon, Google, Facebook, Bloomberg, Microsoft

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.

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 = 5.

Example 2:

Input: prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: Prices only decrease. No profitable transaction is possible.

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

Approach: Greedy One-Pass

Key insight: At each day, the best we could have done is bought at the lowest price seen so far. So track the minimum price seen so far, and the maximum profit achievable if we sell today.

Algorithm:

1. Initialize min_price = infinity, max_profit = 0
2. For each price:
   • Update min_price = min(min_price, price)
   • Update max_profit = max(max_profit, price - min_price)
3. Return max_profit

def maxProfit(prices: list[int]) -> int:
    min_price = float('inf')
    max_profit = 0
    
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    
    return max_profit

Dry Run

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

Day	Price	min_price	price - min_price	max_profit
0	7	7	0	0
1	1	1	0	0
2	5	1	4	4
3	3	1	2	4
4	6	1	5	5
5	4	1	3	5

Result: 5 ✓

Why Greedy Works

We always sell at the highest future price after the cheapest past price. By maintaining the minimum price seen so far and computing the profit at each step, we're implicitly considering every valid (buy, sell) pair where buy_day < sell_day. The maximum over all these is the answer.

Common Mistakes

• Returning a negative profit (it's not allowed — return 0 if no profitable trade)
• Forgetting the constraint that buy must happen before sell (solved by scanning left to right and tracking the minimum so far, not globally)

Variants

• 122 - Best Time to Buy and Sell Stock II: Multiple transactions allowed → greedy: sum all positive daily differences
• 123 - Best Time to Buy and Sell Stock III: At most 2 transactions → DP with 4 states
• 188 - Best Time to Buy and Sell Stock IV: At most k transactions → generalized DP

Edge Cases

• All prices same: profit = 0
• Strictly decreasing: profit = 0
• Single price: profit = 0 (can't buy and sell on the same day)
• Two prices: max(0, prices[1] - prices[0])

Complexity

• Time: O(n) — single pass
• Space: O(1)