~/leetcode $ 121. Best-Time-To-Buy-And-Sell-Stock

First sliding window problem - new month, new problem type… For this problem, we want to know the max profit that we can make given that we know the prices of a given stock overtime. Naively, we cannot just take the min and max value of the list and return the difference as we need to buy the stock before we can sell it (i.e. the min must come before the max).

We can solve this using two pointers (or I guess in sliding window terms, it would be a window spanning days…). The left pointer points to the current min price and the right pointer will move forward to find the max profit that we can earn given the left and right pointers. So initialise the left and right pointers at the start of the list and move the right pointer until we reach the end of the list, keeping track of the max profit that we can earn. When we come across a price that is lower than the price at the left pointer, we can move the left pointer forward to that new min price.

At the end of the iteration, we return the max profit that we have seen.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int l = 0;
        int r = 0;
        int max_profit = 0;

        while (r < prices.size()) {
            max_profit = max(max_profit, prices[r] - prices[l]);
            if (prices[l] > prices[r]) {
                l = r;
            }
            ++r;
        }

        return max_profit;
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

Time Taken: 3m 39s