Find buy/sell prices in array of stock values to maximize positive difference

Magsol_13604 0
Viewed 24192

Got this question in an interview today, and its optimized solution stopped me cold (which blows, because I really wanted to work for this company...)

Given a single array of real values, each of which represents the stock value of a company after an arbitrary period of time, find the best buy price and its corresponding best sell price (buy low, sell high).

To illustrate with an example, let's take the stock ticker of Company Z:

55.39 109.23 48.29 81.59 105.53 94.45 12.24

Important to note is the fact that the array is "sorted" temporally - i.e. as time passes, values are appended to the right end of the array. Thus, our buy value will be (has to be) to the left of our sell value.

(in the above example, the ideal solution is to buy at 48.29 and sell at 105.53)

I came up with the naive solution easily enough with O(n2) complexity (implemented in java):

// returns a 2-element array: first element is the index in the argument array
// of the best buying price, and the second element is the index of the best
// selling price which, collectively, maximize the trading return
//
// if there is no favorable trading (e.g. prices monotonically fall), null is returned
public int[] maximizeReturn(ArrayList<Double> prices) {
  int [] retval = new int[2];
  int BUY = 0, SELL = 1;
  retval[BUY] = retval[SELL] = -1; // indices of buy and sell prices, respectively

  for (int i = 0; i < prices.size(); i++) {
    for (int j = i + 1; j < prices.size(); j++) {
      double difference = prices.get(j).doubleValue() - 
                          prices.get(i).doubleValue();

      if (difference > 0.0) {
        if (retval[BUY] < 0 || difference > prices.get(retval[SELL]).doubleValue() - 
                                            prices.get(retval[BUY]).doubleValue()) {
          retval[BUY] = i;
          retval[SELL] = j;
        }
      }
    }
  }
  return (retval[BUY] > 0 ? retval : null);
}

Here's where I screwed up: there's a linear time O(n) solution, and I completely bombed in trying to figure it out (yeah, I know, FAIL). Does anyone know how to implement the linear time solution? (any language you're comfortable with) Thanks!

Edit

I suppose, for anyone interested, I just received word today that I didn't get the job for which I interviewed where they asked me this question. :(

stocks complexity-theory optimization arrays
24 Answers

Here is my attempt using Javascript. The script computes the answer in O(N): 

//Main Stock Array
var stock = [15, 20, 0, 3, 30, 45, 67, 92, 1, 4, 99];


//Setup initial variable state
var ans = {}, tmp = {}; //These are just for namespacing / syntatic sugar
ans.minVal = stock[0];
ans.minInd = 0;
ans.maxDiff = stock[1] - stock[0];
ans.maxInd = 1;
tmp.minInd = ans.minInd;
tmp.minVal = ans.minVal;

//Basically we iterate throught the array. If we find a new low, we start tracking it. Otherwise we compare the current index against the previously found low
for(i = 1; i <= stock.length-1; i++) {
    if(tmp.minVal > stock[i]) {
        tmp.minVal = stock[i];
        tmp.minInd = i;
    } else {
        ans.diff = stock[i] - stock[tmp.minInd];
        if(ans.diff > ans.maxDiff) { //Looks like we found a new maxDifference. Lets log the indexes
            ans.maxDiff = ans.diff;
            ans.maxInd = i;
            ans.minInd = tmp.minInd;
            ans.minVal = tmp.minVal;
        }
    }
}

document.write('You should buy your stocks on day ' + ans.minInd + ' and sell on day ' + ans.maxInd);
user_11798970

Solution in scala :

Example : [ 7, 2, 5, 6, 1, 3, 6, 4 ]

Keep a pointer to the last minimum stock price(lastStockPrice) and compare it to the current stock price. When you reach a point where the current stock price < last minimun stock price, you update the lastStockPrice.

While looping through the array, keep a track of the max difference (profit) between the currentPrice and the lastStockPrice as the profit can change when you update the lastStockPrice.

The below scala code works in O(n) time and takes a constant amount of space.

object Solution {
    def maxProfit(prices: Array[Int]): Int = {
        var lastStockPrice = Int.MaxValue
        var maxProfit = 0
        for(currentPrice <- prices){
            if(currentPrice < lastStockPrice){
                lastStockPrice = currentPrice;
            }else if(currentPrice - lastStockPrice > maxProfit){
                maxProfit = currentPrice - lastStockPrice;
            }
        }
        maxProfit
    }
}
user_13122260

The logic to solve this problem is same as "max subarray problem" using Kadane's Algorithm. Since no body has mentioned this so far, I thought it's a good thing for everybody to know.

All the straight forward solution should work, but if the interviewer twists the question slightly by giving the difference array of prices, Ex: for {1, 7, 4, 11}, if he gives {0, 6, -3, 7}, you might end up being confused.

Here, the logic is to calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array, and find a contiguous subarray giving maximum profit. If the difference falls below 0, reset it to zero.

class Solution:
def maxProfit(self, prices: List[int]) -> int:
    
    _currmax = 0
    _globalMax = 0
    
    for i in range(1,len(prices)):
        
        _currmax = max(_currmax+(prices[i]-prices[i-1]),0)
        _globalMax = max(_globalMax,_currmax)
        
    return _globalMax
user_85431160
Related