Best Time to Buy and Sell Stock

• Difficulty: Easy
• Topics: Array, Dynamic Programming
• Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Problem Description

You are given an array prices where prices[i] is the price of a given stock on the ith 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) 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, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

Solution

1. Problem Deconstruction

Technical Restatement
Given an array prices where prices[i] represents a stock price on day i, compute the maximum profit achievable by buying on day i and selling on day j where j > i. If no profit is possible, return 0.

Beginner-Friendly Explanation
Imagine tracking stock prices over several days. Your goal is to buy low and sell high, but you must buy before selling. Determine the best pair of days to maximize your profit. If prices only decrease, you make no transaction and profit $0.

Mathematical Formulation
Let P be the array of prices. Find:

$$\max \left( P[j] - P[i] \right) \quad \text{where} \quad 0 \leq i < j < n$$

Subject to:

$$P[j] - P[i] > 0 \quad \text{(else return 0)}$$

Constraint Analysis

1. Array Length (1 ≤ n ≤ 1e5):
   • Eliminates O(n²) brute-force approaches. Requires O(n) or O(n log n) solutions.
2. Price Values (0 ≤ P[i] ≤ 1e4):
   • Zero prices require no special handling beyond standard arithmetic.
   • Implicit edge case: All prices zero → profit $0.

---

2. Intuition Scaffolding

Analogies

1. Real-World (Concert Tickets):
   Buy tickets early when prices drop, sell later when demand surges.
2. Gaming (RPG Potions):
   Purchase potions at the lowest market price, sell after boss fights spike demand.
3. Math (Maximum Delta):
   Track cumulative minimum and compute forward deltas.

Common Pitfalls

1. Global Min/Max Fallacy:
   Global min might occur after global max (invalid transaction).
2. Overlapping Windows:
   Checking only adjacent days misses longer-term opportunities.
3. Early Termination:
   Stopping after finding one profit misses larger later profits.
4. Negative Profit Ignored:
   Correctly default to $0 when no profitable trades exist.
5. Single-Pass Complexity:
   Misunderstanding how to track state in O(1) space.

---

3. Approach Encyclopedia

Brute Force (Theoretical)

def maxProfit(prices):  
    max_profit = 0  
    for i in range(len(prices)):  
        for j in range(i+1, len(prices)):  
            profit = prices[j] - prices[i]  
            if profit > max_profit:  
                max_profit = profit  
    return max_profit  

Complexity:

• Time: O(n²) → 1e10 operations (impossible for n=1e5).
• Space: O(1).

Optimal Single-Pass Approach
Pseudocode:

Initialize min_price to infinity  
Initialize max_profit to 0  
For each price in prices:  
    if price < min_price:  
        Update min_price  
    else:  
        Compute profit = price - min_price  
        Update max_profit if profit is larger  
Return max_profit  

Complexity Proof:

• Time: O(n) → Each price processed once.
• Space: O(1) → Two variables.

Visualization

Prices: [7, 1, 5, 3, 6, 4]  
         ↓ Buy here (min=1)  
                ↑ Sell here (profit=5)  

---

4. Code Deep Dive

Optimal Solution Code

def maxProfit(prices):  
    min_price = float('inf')  # Track lowest price seen so far  
    max_profit = 0  # Track maximum achievable profit  
    for price in prices:  
        if price < min_price:  
            min_price = price  # New buying opportunity  
        else:  
            profit = price - min_price  
            if profit > max_profit:  
                max_profit = profit  # Update best sell timing  
    return max_profit  

Line-by-Line Explanation

1. min_price = float('inf'):
   • Initialized to infinity to ensure first price becomes the minimum.
2. max_profit = 0:
   • Default profit when no transactions are possible.
3. Loop Through Prices:
   • For each day, decide whether to update the buy point or compute profit.
4. if price < min_price:
   • Found a new potential entry point for buying.
5. else: Block:
   • Compute profit if selling at current price using the historical minimum.

Edge Case Handling

• Example 2 (All Decreasing):
  min_price updates each day, but no profit is computed → returns 0.
• Single-Day Array: Loop runs once, max_profit remains 0.

---

5. Complexity War Room

Hardware Considerations

• 1e5 elements → ~400KB memory (assuming 4-byte integers). Fits in CPU cache.
• Single-pass algorithm minimizes cache misses.

Approach Comparison

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n²)	O(1)	9/10	❌ Fails for n=1e5
Single-Pass	O(n)	O(1)	10/10	✅ Optimal Solution

---

6. Pro Mode Extras

Variants

• Multiple Transactions (LC 122): Buy/sell multiple times (peak-valley approach).
• Two Transactions (LC 123): Dynamic programming with state tracking.
• Cooldown Period (LC 309): Finite state machines with rest periods.

Interview Cheat Sheet

• First Mention: Time/space complexity.
• Key Insight: Track minimum price and compute deltas.
• Test Cases: All decreasing, all increasing, single peak, zero prices.