Best ⏳ to Buy and Sell 📉

Best Time to Buy and Sell Stock: The Time Traveler’s Dilemma 🕰️💰

The Story

• You’re a time traveler with insider knowledge of stock prices, but there’s a catch - you can only make ONE transaction (buy once, sell once). Your mission: maximize profit like a financial wizard! 🧙‍♂️

The Drama 🎬

• Naive Approach : “Let me check every possible buy-sell combination!” O(n²) screaming in the distance 😱

• Smart Approach : “I’ll track the lowest price I’ve seen so far!” O(n) enters like a boss 😎

The Algorithm (aka “The Regret Minimization Strategy”)

• Start Poor : Begin with 0 profit and assume first day price is the minimum.
• Daily Routine : For each day, ask two questions:
  • “Is today’s price the cheapest I’ve ever seen?” (Update minimum)
  • “If I sold today, would I make more profit than my best scenario so far?” (Update max profit)
• Keep Walking : Continue this “shoulda-coulda-woulda” analysis for all days.
• Final Answer : Return your maximum possible profit

The Punchline 🤡

// It's like saying: "I wish I bought at the lowest and sold at the highest!"
// But we can only know this by looking at each day and thinking:
// "What if I had bought at the cheapest day so far and sold today?"

Fun Fact 🎭

• If all prices are decreasing, you return 0 - because sometimes the best trade is no trade! It’s like saying “I’ll just keep my money in my mattress, thank you very much!” 🛏️💵

Memory Palace 🏰

• minPrice = Your time machine bookmark (cheapest day you’ve witnessed)
• maxProfit = Your crystal ball vision (best profit possible so far)
• One pass = You’re living day by day but learning from yesterday!

Complexity: O(n) time, O(1) space - because being a smart investor doesn’t require a huge brain, just a good memory! 🧠✨

The Actual Code (Your Wall Street Algorithm) 🏦

  const maxProfit = (prices) => {
    let minPrice = prices[0]   // "This is the cheapest so far" 💸
    let maximumProfit = 0      // "I haven't made money yet" 😢
    for(let i=0; i<prices.length; i++){
      if(prices[i] < minPrice){
        minPrice = prices[i]     // "Wow, even cheaper!" 📉
      }
      else{
        // "What if I bought at minPrice and sold today?"
        maximumProfit = Math.max(maximumProfit, prices[i] - minPrice) // 📈
      }
    }
    return maximumProfit  // "Here's the best I could do!" 💰
  }

Test Drive 🚗

// Example: prices = [7,1,5,3,6,4]
// Day 0: minPrice=7, maxProfit=0
// Day 1: price=1 < 7, so minPrice=1, maxProfit=0
// Day 2: price=5 > 1, profit if sold = 5-1 = 4, maxProfit=4
// Day 3: price=3 > 1, profit if sold = 3-1 = 2, maxProfit=4 (no change)
// Day 4: price=6 > 1, profit if sold = 6-1 = 5, maxProfit=5 🎯
// Day 5: price=4 > 1, profit if sold = 4-1 = 3, maxProfit=5 (no change)
// Result: 5 (buy at 1, sell at 6)