optimized.cpp

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

class Solution {
public:
    /*
     * 121. Best Time to Buy and Sell Stock - Optimized Solution
     * 
     * Approach:
     * - One Pass (Sliding Window / Greedy)
     * - We need to find the maximum difference between two numbers where the smaller number appears before the larger number.
     * - Keep track of the minimum price seen so far (`minPrice`).
     * - Iterate through the prices:
     *   - If current price is lower than `minPrice`, update `minPrice`.
     *   - Else, calculate the potential profit (current price - `minPrice`) and update `maxProfit` if it's higher.
     * 
     * Time Complexity: O(n) - Single pass through the array.
     * Space Complexity: O(1) - Constant extra space used.
     */
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int maxProfit = 0;
        
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else {
                int profit = price - minPrice;
                if (profit > maxProfit) {
                    maxProfit = profit;
                }
            }
        }
        
        return maxProfit;
    }
};