📈 Best Time to Buy and Sell Stock (LeetCode 121)

🧠 Problem Statement

You are given an array prices where prices[i] represents the price of a given stock on the i-th day.

Your goal is to maximize profit by choosing a single day to buy one stock and a different future day to sell that stock.

If no profitable transaction is possible, return 0.

🧾 Examples

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: No future price is higher than the earlier prices.

🔍 Constraints

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

💡 Intuition

We need to buy low and sell high, but with a key restriction:

We must buy before we sell.

So we’re looking for the maximum difference between two prices prices[j] - prices[i] where j > i.

🪜 Step-by-Step Approach

🔁 One-Pass Greedy Algorithm

Track the minimum price so far as you iterate.
For each price, calculate the profit if you bought at the minimum and sold today.
Keep updating the maximum profit found.

✅ Why this works

We always look backward to see the best time we could have bought the stock before today.

This ensures we never violate the "buy before sell" rule.

🧮 Dry Run

Let's walk through prices = [7, 1, 5, 3, 6, 4]

Day	Price	Min Price So Far	Profit if Sold Today	Max Profit
1	7	7	0	0
2	1	1 ✅	0	0
3	5	1	4	4 ✅
4	3	1	2	4
5	6	1	5 ✅	5 ✅
6	4	1	3	5

🧑‍💻 C++ Code

#include <vector>
#include <algorithm>
using namespace std;

int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX;
    int maxProfit = 0;

    for (int price : prices) {
        minPrice = min(minPrice, price); // Track lowest price so far
        maxProfit = max(maxProfit, price - minPrice); // Check today's profit
    }

    return maxProfit;
}

🧑‍💻 Java Code

public class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            minPrice = Math.min(minPrice, price); // Track lowest price so far
            maxProfit = Math.max(maxProfit, price - minPrice); // Check today's profit
        }

        return maxProfit;
    }
}