LeetCode 121. Best Time to Buy and Sell Stock

Problem Statement: You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1

Input: prices [6, 1, 4, 5, 2]
Output: 4
Explanation: Buy on day 2 (price = 1) and sell on day 4(price = 5), 
profit = 5-1 = 4. Note that buying on day 2 and selling on day 1 is
not allowed because you must buy before you sell.

Example 2

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

SOLUTION: This problem can be solved using two pointers that act as a sliding window in a linear run time.

Let’s consider [6, 1, 4, 5, 2] as our input (stock prices from day 1 to day 5) represented in the following graph:

Graph representing the stock prices from day 1 to day 5

So how do we find the maximum profit? We loop through the array first by buying the stock at day 1 at 6$ (that’s our left pointer or buying price). And check the price at day 2 which is 1$ (the right pointer or selling price). Now, we will have two cases.

Profitable Case: If the price at right pointer (selling price = 1$) is greater than the price at the left pointer (buying price = 6$), then we check for profit. In our example it’s not, so we don’t check for profit.

Non-Profitable Case: Otherwise (selling price < buying price), we don’t have to check the profit because it will be negative (1$ -6$ = -5$) and from the problem statement profit can’t be lass than 0. In this case, we change the left pointer to right pointer (left pointer = right pointer). So, in our example, our buying price updates to 1$.

And finally (once we check both cases), we move the right pointer to next day. Or in our example, our selling price becomes 4$.

At this point, we are at the end of the loop, and we repeat the process.

Note that we update the left pointer (buying price) to right only when there is decrease in price. Otherwise, we won’t change the left pointer. This is because we want to go to the lowest buying price.

The pseudo code:

left = buying price
right = selling price

for all the elements in array
    if right is greater than left then
        calculate the profit
        check and update the profit
    else (right is lower than the left)
        change left to right
    increment right

return maxprofit

Code in C++:

int maxProfit(vector<int>& prices) {
        if (prices.size() == 1){
            return 0;
        }

        int l = 0;  // left = buying price
        int r = 1;  // right = selling price

        int maxProfit = 0;

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

Time Complexity: O(n)

Space Complexity: O(1)