121. Best Time to Buy and Sell Stock

📝 Problem Details

• Title: 121. Best Time to Buy and Sell Stock
• Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
• Difficulty: Easy
• Tags/Categories: Sliding-Window

input array prices where prices[i] represents the stock price on day [i] you can only buy and sell once, and you must buy before you sell return the maximum profit you can achieve , or 0 if no profit is possible

💭What Were My Initial Thoughts?

- naive approach:
	- check every possible pair of buy and sell days O(n^2)
- since we must buy before we sell, we need to find the lowest price before the current day
- suggests using a sliding window approach, tracking the minimum price while iterating

💡 Explanation of Solution

sliding window approach:
- init two pointers left and right
	- left = 0
	- right iterates through the array (the day to sell)

- init profit = 0

- for each prices at index right:
	- if prices[right] < prices[left]
		- update left = right (new lowest prices)
	- otherwise, computet the profit and take the max between itself and the current max

- return the max profit found

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int left = 0;  // Start of the "window" (buy day)
        int profit = 0; // Maximum profit
 
        for (int right = 1; right < prices.size(); ++right) {
            // If the current price is less than the price at 'left', move 'left' to 'right'
            if (prices[right] < prices[left]) {
                left = right; // Update the minimum price day
            } else {
                // Calculate the profit and update the maximum profit
                profit = max(profit, prices[right] - prices[left]);
            }
        }
 
        return profit; // Return the maximum profit
    }
};