Best Time to Buy and Sell Stock

This question is one of the 75 most frequently asked on LeetCode, focusing on maximizing profit. Essentially, it involves buying a stock on any given day and selling it on that day or in future days, with the constraint that selling cannot occur before buying. The goal is to determine the maximum profit achievable from this transaction.

Example 1:

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.

Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Greedy approach

In this approach, you can declare and initialize a variable to the first element of the array. As you iterate through the array, if the current price is smaller than the variable, you buy on the ith day. This method allows you to track the minimum price encountered so far. Ultimately, the maximum profit can be determined and returned based on this approach.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = 0; // Left Pointer
        int sell = 1; // Right Pointer
        int maxProfit = 0;
        while(sell < prices.size()){
            if(prices[buy] < prices[sell]){
                int profit = prices[sell] - prices[buy];
                maxProfit = max(maxProfit, profit);
            }else{
                buy = sell;
            }
            sell  = sell + 1;
        }
        return maxProfit;
    }
};

• Time Complexity: O(N). Where N is the size of array.
• Auxiliary Space: O(1)