Coding interview Essentials

19. Best time to buy and sell stock

Best time to buy and sell stock

Introduction

The problem discussed in this chapter is not particularly difficult as it is easily solvable in quadratic time using a brute-force algorithm. However, a more efficient solution is possible and, given that this is exactly the type of question for which interviewers expect fast and elegant solutions, it’s worth taking the time to become familiar with the problem structure and the best approaches to solving it.

Problem statement

You are given prices for a stock for a number \(n\) of days. The prices are stored in an array \(P\) of length \(n\) where each cell \(i\) of the array contains the price for the stock on the \(i^{th}\) day. You are only permitted to perform one buy and one sell operations. What is the maximum profit you can achieve given the prices for the stock in \(P\)?

You have to perform the buy operation before the sell operation. You cannot buy the stock on the day and sell on the .


Given the array of prices for the stock is: \([7,1,5,3,6,4]\), the answer is \(5\). You can buy on the day and sell on the .


Given the array of prices for the stock is: \([6,5,4,3,2,1]\), the answer is \(0\). There is no way you can make a profit higher than \(0\) i.e. not buying and not selling.

Clarification Questions

Can you perform the buy and sell operation on the same day?

Yes, that is possible.

Discussion

A profit is achieved when a buy and sell transaction are performed with prices \(p_b\) and \(p_s\) respectively and \(p_b \leq p_s\). In other words, our goal is to buy at a lower price than we sell. The maximum profit is obtained whenever the spread between those two prices is maximum i.e. \(\max_{}{(p_s - p_b)}\)

Brute-force

The brute force approach is very straightforward as the only thing we need to do is apply the definition of maximum profit we discussed earlier. For all pairs of ordered index \(i \leq j\) we can calculate \(P_i - P_j\) and return the maximum among all those profit values. Listing [list:buy_sell_stocks:bruteforce] shows an implementation of this approach. Note that a profit of \(0\) is always possible by either not performing any transaction or simply performing the buy and sell on the same day. Thus \(j = i+1\), because it is pointless to calculate the profit for the same day as we know already it will always be \(0\). For this reason we also limit the buy operation to the day before (\(i< n-1\)) the last, because if we want to have any chance of making a profit we need to at least have one day left after the buy to perform the sell operation.

Listing 1: Brute force $O(n^2)$ solution to the problem of buying and selling stock.

int buy_sell_stocks_bruteforce(std::vector<int> &P)
{
  const int n = P.size();
  int ans     = 0;
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
      ans = std::max(ans, P[j] - P[i]);
  return ans;
}

Linear time solution

The solution above can be improved if we look at the problem from slightly different angle. The idea is that we can process the array from the last day to the first and, for each of the days, calculate the best profit to be made by selling on any of the days already processed (which occurs later in time).

We keep a variable \(b\) with the maximum price seen so far which is initially \(-\infty\). The algorithm starts from day \(n\) and for each day checks whether buying that day and selling at the price \(b\) (the highest price seen so far) would improve the profit found thus far. This approach is correct because the maximum profit happens when the spread between sell and buy price is maximum. The implementation of the idea above is shown in Listing [list:buy_sell_stocks:linear].

Listing 2: Dynamic programming linear time, constant space solution to the problem of buying and selling stock.

int buy_sell_stocks_DP(std::vector<int> &P)
{
  const int days     = P.size();
  int highest_so_far = std::numeric_limits<int>::min();
  int ans            = 0;
  for (int i = days - 1; i >= 0; i--)
  {
    highest_so_far = std::max(highest_so_far, P[i]);
    ans            = std::max(ans, highest_so_far - P[i]);
  }
  return ans;
}

Common Variations - Multiple Transactions

Problem statement

This problem is a variation of the problem presented in Section 23.1 where we are allowed to make as many transactions as we like. The question remains the same: what is the maximum profit achievable?

Note that you may not engage in multiple transactions at the same time i.e., you must sell the stock before you buy again.

[ex:buy_sell_stocks_2:exmaple1]
Given the array of prices for the stock is: \([7,1,5,3,6,4]\), the answer is \(7\). You can buy on the day and sell on the and then engage on a second transaction where you buy on the day and sell on the .

Discussion

This might seems like an harder problem at first than the version presented in Section 23.1 but in reality as we will see in Section 23.7 its solution is actually easier.

Brute force solution

As usual we start our discussion by quickly presenting the brute force solution. In this case this means trying all possible sets of transactions (a valid pair of buy and sell operation not overlapping with any other transaction). We can try all possible sets by using recursion cleverly. However this approach will not take us far because the number of possible sets of transaction grows exponentially. We are showing this approach in Listing [list:buy_sell_stocks_2:bruteforce] only because we think its implementation can be somehow instructive.

Listing 3: Bruteforce exponential solution to the problem of buying and selling stock with no limits on the number of transactions.

int buy_sell_stocks_multiple_transactions_exp_helper(const std::vector<int> &P,
                                                     const int start)
{
  const int *x = nullptr;
  int ans      = 0;
  for (int buy_day = start; buy_day < std::ssize(P) - 1; buy_day++)
  {
    for (int sell_day = buy_day + 1; sell_day < std::ssize(P); sell_day++)
    {
      if (P[buy_day] < P[sell_day])  // pointless to sell otherwise
      {
        x                        = &P[0];
        const int selling_profit = P[sell_day] - P[buy_day];
        const int profit_rest_transactions =
            buy_sell_stocks_multiple_transactions_exp_helper(P, sell_day + 1);
        ans = std::max(ans, selling_profit + profit_rest_transactions);
      }
      else
      {
        ans = x != nullptr ? *x : 0;
      }
    }
  }
  return ans;
}

int buy_sell_stocks_multiple_transactions_exp(const std::vector<int> &P)
{
  return buy_sell_stocks_multiple_transactions_exp_helper(P, 0);
}

Linear time solution

The idea is simple and it is clearer once we look at prices plotted on a graph. As you can see in Figure 55, the data is made of peaks and valleys (unless the data is fully increasing or decreasing). Those are the point of interests because if we buy at valleys and sell at peaks we are able to obtains the maximum profit. One can simply loop thought the array and identify those peaks and valleys and calculate the total profit as the sum of the profits along those point of interests. For instance w.r.t. the example [ex:buy_sell_stocks_2:exmaple1] there are two pairs valley-peak happening at days \(2\) and \(3\) and days \(4\) and \(5\), respectively. But, what is a valley and/or a peak exactly? A day \(i\) is a valley if \(P_i < P_{i-1}\) and \(P_i > P_{i+1}\) while is a peak if \(P_i > P_{i-1}\) and \(P_i < P_{i+1}\). So all it is needed is to identify those pairs of valleys and peaks and we are done.

But do we really need to find peaks and valleys? The answer is not as all it is necessary is to make sure we cash at all opportunities we have i.e. in all those cases where we can buy at a lower price we sell. Thus we can process days two at the time and, since there is no limit on the number of transactions, simply buy and sell whenever the spread between buy and sell price is convenient.

The idea above can be implemented as shown in Listing [list:buy_sell_stocks_2:linear].

Listing 4: $O(n)$ time and $O(1)$ space solution to the problem of buying and selling stock with no limits on the number of transactions.

int buy_sell_stocks_multiple_transactions_lin(std::vector<int> &P)
{
  int ans = 0;
  for (int i = 0; i < (int)P.size() - 1; i++)
  {
    if (P[i] < P[i + 1])
      ans += (P[i + 1] - P[i]);
  }
  return ans;
}