How to make algorithms more efficient?

Question

I tried to solve the following problem : Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell.

But I was only able to come up with an O(n^2) solution. I understood the solution when I saw it but I wouldn't have been able to come up with the O(n) solution. Can I get some tips on optimizing my algorithms?

Answer 1

Like many crafts, this is a matter of experience, I guess. In this particular case, a good hint towards a linear time solution is to look for some algorithm that maintains a constant number of variables which during a scan provide enough information to answer the question "from the sequence's start to the current position. But even to that end, you need to understand what kind of information you look for. A "strategic" approach would be to ask for helpful information from the solution to the problem:

1) you could answer the question in linear time if you had an array of maximum profits für each index as selling point(simply scan for the maximum).

2) you could compute the maximum profit for each selling point if you had an array of minimum value in the subarray ending at each index.

3) carrying the minimum value in the subarray ending at each index is easy in linear time.

Answer 2

My solution is an algorithm with linear O(N) complexity.

you have to trace following index information

• best sell time
• best buy time
• lowest price time
• maximum profit

The idea is simple. First, Set 'best buy time' to 0. Iterate an array and change the 'lowest price time' index if index meets a lower share price. This is a potential timing that you can earn a higher profit.

Also, update a maximum profit when the difference between share[index] - share[min] is higher than current value. Keep in mind 'minimum share' index and 'buy time' are totally different.

c++ implementation

pair<int, int> bestTradeTime(vector<int>& shares){
   int min = 0;
   int buy, sell, maxProfit=0;

   for(int i=1; i<n; i++){
      //If minimum price is found, update it. 
      //In this case, there is no way the profit is higher than maxProfit
      if(shares[min] > shares[i])
        min = i;

      //When finding maximum profit, update it. 
      else if(shares[i] - shares[min] > maxProfit){
        maxProfit = shares[i] - shares[min];
        buy = min;
        sell = i;
      }
   }
   return make_pair(buy, sell);
}

Answer 3

This was asked to me in an interview and I came up with the following logic:

My idea was to make a suffix array to get the optimized price to sell stock. So, if I buy the stock at price[i], the optimum solution is to sell the stock in

value = max(price[i+1], price[i+2], ... , price[n-1]);

So, reverse traversing the array I found the maximum of the price[(i+1) .. (n-1)] in O(n) time. After this array is filled, I can just forward traverse the array one more time to calculate the maximum profit and return it. The complexity of this solution is O(n).

Here is my C++ implementation.

// Assuming the prices vector to be the prices of stock at different time
// instances. Also, I have assumed that we have to buy within values
// prices[0..(n-2)] and sell within values prices[1..(n-1)].

#include <iostream>
#include <algorithm>
#include <vector>

int max_profit(std::vector <int> prices) {
    int n = prices.size(), profit = 0, b = -1, s = -1;

    // sell[i] = the price at which you should sell when you buy the stock at
    // prices[i] = max(prices[(i+1)...(n-1)]);
    // position[i] = the position at which sell[i] is stored in prices[i].

    std::vector <int> sell (n-1), position (n-1);
    sell[n-2] = prices[n-1];
    position[n-2] = n-1;
    for(int i = n-3; i >= 0; i--) {
        if(sell[i+1] > prices[i+1]) {
            sell[i] = sell[i+1];
            position[i] = position[i+1];
        }
        else {
            sell[i] = prices[i+1];
            position[i] = i+1;
        }
    }

    for(int i = 0; i < n-1; i++) {
        if(sell[i+1] - prices[i] > profit) {
            profit = sell[i+1] - prices[i];
            b = i;
            s = position[i+1];
        }
    }
    std::cout << "Buy at position: " << b << std::endl;
    std::cout << "Sell at position: " << s << std::endl;
    return profit;
}

int main() {
    int profit = max_profit(std::vector <int> {3, 9, 1, 7, 2, 5, 8, 4, 0});
    std::cout << profit << std::endl;
    return 0;
}

The sad part was this question was given to me before the interview and when the interview started, we didn't even discuss this solution.

An interesting version of this question is to buy and sell two different stock in the pattern Buy Sell Buy Sell (we cannot do Buy Buy Sell Sell) and get the maximum profit.

Answer 4

You can implement a simple algorithm with linear O(N) complexity. Imagine that you have an array with prices, e.g.

   3 9 1 7 2 5 8 4 0

you have to scan the array while tracking

 - best buy index
 - best sell index
 - lowest price index

read the current index (i) and value (price), then check

 // do we have a lower price than ever?
 if (price < prices[lowest price index])
   lowest price index = i;

 // can we sell for a better price?
 if (price > prices[best sell index])
   best sell index = i;

 // shall we switch from the best buy index to the lowest price index?
 if (prices[best sell index] - prices[best buy index] < price - prices[lowest price index])
   best buy index = lowest price index;
   best sell index = i;  

C# implementation:

private static Tuple<int, int> BestTimes(double[] prices) {
  int bestBuyIndex = 0;   // buy at the opening
  int bestSellIndex = 0;  // ...and sell it immediately (with profit 0)

  int lowestBuyIndex = 0;

  for (int i = 0; i < prices.Length; ++i) {
    double price = prices[i];

    if (price > prices[bestSellIndex])
      bestSellIndex = i;

    if (price < prices[lowestBuyIndex])
      lowestBuyIndex = i;

    if (price - prices[lowestBuyIndex] >= prices[bestSellIndex] - prices[bestBuyIndex]) {
      bestBuyIndex = lowestBuyIndex;
      bestSellIndex = i;
    }
  }

  return new Tuple<int, int>(bestBuyIndex, bestSellIndex);
}

Test:

double[] prices = new double[] { 3, 9, 1, 7, 2, 5, 8, 4, 0 };

Tuple<int, int> solution =  BestTimes(prices);

Console.Write($"Buy at {solution.Item1} (price {prices[solution.Item1]}) ");
Console.Write($"Sell at {solution.Item2} (price {prices[solution.Item2]}) ");

Outcome is

Buy at 2 (price 1) Sell at 6 (price 8)