Best time to Buy and Sell Stocks - A comprehensive Guide

Best time to buy and sell stocks is one of the most popular type of problem series asked in various interviews.

The problem basically consists of the prices of stocks on each day and requires us to find the maximum profit that can be obtained by buying and selling these stocks based on some condition given in the problem.

There are six different buy and sell problems with difficulty level slightly increasing in each, based on different conditions for buying/selling.

Lets understand how to approach these problems and become proficient in solving this problem series!

Best Time to Buy and Sell Stock I

Leetcode Problem: 121

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.

This is the easiest problem wherein we have to buy and sell stock only once such that we obtain maximum profit (we have to buy before we sell).

The idea is that as we traverse through prices each day, we buy when we find the stock the cheapest and sell when we find it most expensive.

   int maxProfit(vector<int>& prices) {

        int profit=0,min=prices[0];

        for(int i=0;i<prices.size();i++){
            if(prices[i]<min)
                min=prices[i];
            else
                profit=max(profit,prices[i]-min);
        }

        return profit;
    }

We try to buy at our local minimum. As we traverse through prices, if the current price is less than the local minimum, we update our local minimum. Else if the current price is greater, we calculate the profit on selling the current price. If the profit is greater than the earlier profit, we update our result.

Best Time to Buy and Sell Stock II

Leetcode Problem: 122

You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

While the first problem allowed us to buy and sell only once, this time we are allowed to buy and sell as many times as we like. The only constraint is that we have to sell our stock before buying again.

The idea is to keep on selling stock whenever it is possible and adding the profit. This is known as peak valley approach. Refer to the Leetcode diagram below to understand better.

Whenever we come across peak, the price of stock is greater than in the previous day, hence we sell. And the profit of this transaction becomes peak - valley. The net profit is the sum of all such peak - valley transactions.

Now someone might try to skip a peak to try to obtain more profit later. But in doing so, we end up losing the profit of a transaction, leading to an overall lesser profit.

For example, if in the example given above, we skip peaki and valleyj to get a profit from peakj - valleyi, we observe that this net profit C is less than that of A + B.

Hence, it is important to sell at a peak that is immediately following a valley. Below is the implementation of this approach.

int maxProfit(vector<int>& prices) {

        int max_profit=0;

        for(int i=1;i<prices.size();i++){
            if(prices[i]>prices[i-1]){
                max_profit+=prices[i]-prices[i-1];
            }
        }

        return max_profit;
    }

Best Time to Buy and Sell Stock III

Leetcode Problem: 123

You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

In the previous problem, we had the freedom of performing as many transactions as we liked, i.e., we had sold as many times as possible to obtain maximum profit. But this question limits our transactions to 2 times. We have to find the maximum profit that is possible by buying/selling at most twice!

Since we can sell two times, the idea is to divide the problem into two parts. In the first part, we store the different profits possible from different transactions of transaction 1. And in second part we calculate the profit obtained from non-overlapping transactions of transaction 2, and find the maximum profit sum.

Approach:

Create an array profit of size n.
Traverse prices from right to left and keep storing the maximum attainable profit on each day in the profit array, i.e., profit[i] contains maximum achievable profit from prices i till n-1. These are the profit values for any transaction 1.
Now for performing transaction 2, traverse prices from left to right and calculate the maximum profit attainable here. This transaction 2 at any i gives us profit from prices 0 till i.
Add profit of both transactions at i. Note: Transactions 1 and 2 for any i are non overlapping as transaction 2 gives us maximum profit from 0 till i, and transaction 1 gives us maximum profit from i till n-1 , and hence both can be added.
Update profit[i] with current maximum profit. If the obtained profit sum of both transactions at i is greater than profit[i-1], this is our new maximum profit. Else profit[i-1] is still the current maximum profit.
Profit[n-1] finally contains the maximum profit value. Return this as your result.

   int maxProfit(vector<int>& prices) {

        int n = prices.size();
        int profit[prices.size()];

        memset(profit,0,sizeof(profit));
        int max_price=prices[n-1];

        for(int i=n-2;i>=0;i--){
            if(prices[i]>max_price) max_price=prices[i];
            profit[i] = max(profit[i + 1], max_price - prices[i]);
        }

        int min_price=prices[0];

        for (int i = 1; i < n; i++) {
            if (prices[i] < min_price) min_price = prices[i];
            profit[i] = max(profit[i - 1], profit[i] + (prices[i] - min_price));
        }

        int res=profit[n-1];

        return res;
    }

Best Time to Buy and Sell Stock IV

Leetcode Problem: 188

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k. Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

This is a generalized version of problem 3. Now instead of 2, we have to find maximum profit for at most k transactions.

This requires a simple dynamic programming approach. The idea is that if we don't have a stock, we can buy it and if we have a stock we can sell it. We calculate the profit after buying and selling an item and keep storing it if it is larger than the previous profit value. We perform this k times for each stock.

Approach:

Create 2 arrays, one for storing cash in hand after buying a stock and the other for storing profit after selling a stock.
For every stock, calculate cash in hand after buying and selling it in the two arrays. This is done in a loop j from k till 1 where j denotes the cash in hand after jth buy and sell.
If the current profit after buying at j is greater than the value already stored in profit_after_buying[j], it means that buying this item at jth transaction leaves us with more cash in hand. Hence update this value in profit_after_buying[j]. Do the same for array calculating profit after selling.
profit_after_selling[k] contains the maximum profit obtained after k transactions. Return this value.

Lets see its implementation to understand better.

int maxProfit(int k, vector<int>& prices) {

        int n = prices.size();
        vector<int> profit_after_buying(k + 1, INT_MIN), profit_after_selling(k + 1, 0);

        for (int i = 0; i < prices.size(); ++i) {
            int cur_price = prices[i]; 
            for (int j = k; j >= 1; --j) {
                profit_after_buying[j] = max(profit_after_buying[j], profit_after_selling[j-1] - cur_price);
                profit_after_selling[j] = max(profit_after_selling[j], profit_after_buying[j] + cur_price);
            }
        }
        return profit_after_selling[k];
    }
};

profit_after_buying stores the maximum cash that we have after jth buy. profit_after_selling stores the maximum profit after selling jth item. We keep on performing the above mentioned steps until we get our result!

The next two variations of Buy and Sell series are a little more complicated. So we will cover those in part 2 of this article.

Until then, understand the concept of the four problems explained here and try to implement it yourself!