Best Time to Buy and Sell Stock

You are given an integer array prices where prices[i] represents the price of a stock on the iᵗʰ day.

You want to maximize your profit by choosing one day to buy the stock and a different day in the future to sell it.

Return the maximum profit you can achieve.
If you cannot make any profit, return 0.

🧩 Example:

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.

🐢 Brute Force Approach

💡 Idea:

Try every possible pair of buy and sell days and calculate all profits, then take the maximum.

💻 Code:

function maxProfit(prices) {
  let maxProfit = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      let profit = prices[j] - prices[i];
      if (profit > maxProfit) {
        maxProfit = profit;
      }
    }
  }
  return maxProfit;
}

⏱️ Time Complexity:

• O(n²) — two nested loops.

💾 Space Complexity:

• O(1) — no extra data structures.

⚡ Optimized Approach (One-Pass Solution)

💡 Idea:

Keep track of:

• the minimum price so far, and
• the maximum profit achievable at each step.

You only need one traversal.

💻 Code:

function maxProfit(prices) {
  let minPrice = prices[0];
  let maxProfit = 0;

  for (let i = 1; i < prices.length; i++) {
    let profit = prices[i] - minPrice;
    maxProfit = Math.max(maxProfit, profit);
    minPrice = Math.min(minPrice, prices[i]);
  }

  return maxProfit;
}

⏱️ Time Complexity:

• O(n) — single traversal.

💾 Space Complexity:

• O(1) — only two variables used.

🧠 Learning / Key Takeaways

1. Brute force checks all possibilities, but is inefficient for large inputs.
2. Optimization through observation:
   • Instead of rechecking all pairs, track the lowest buy price so far.
   • Compute profit dynamically for each day.
3. Greedy approach: Always make the best local choice (lowest price, highest profit) to reach the global maximum.
4. This pattern — “track min/max and compute on the fly” — is reusable in problems like:
   • Maximum difference between two elements
   • Kadane’s algorithm (max subarray sum)
   • Temperature rise or price change patterns