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

Question

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(n²) 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. :(

Answer 1

Here's an attempt (C++). Basically everytime I track a new top, I try to see if thats the best profit thusfar. I know that the "bottom" must have been discovered earlier. At that point I remember the top, bottom, and the current max profit. If a new bottom is discovered later, its AFTER the current top, so we must reset top and see if a slightly lower "top" can yield better profit.

#include <iostream>

int main()
{

    double REALLY_BIG_NO = 1e99;
    double bottom = REALLY_BIG_NO; // arbirtrary large number
    double currBestBuy = 0.0;
    double top = 0.0;
    double currBestSell = 0.0;
    double profit = 0.0;

    // array of prices
    double prices[] = {10.50, 55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24, 152.0, 2, 170.0};
    int numPrices = 10;// number of prices

    for (int i = 0; i < numPrices; ++i)
    {
         if (prices[i] < bottom)
         {
            bottom = prices[i];
            // reset the search on a new bottom
            top = 0.0;
         }
         else if (prices[i] > top)
         {
            top = prices[i];
           // calculate profit
            double potentialProfit = (top - bottom);
            if (potentialProfit > profit &&
                bottom != REALLY_BIG_NO)
            {
                profit = potentialProfit;
                currBestSell = top;
                currBestBuy = bottom;
            }
         }
    }

    std::cout << "Best Buy: " << currBestBuy << "Best Sell: " << currBestSell << std::endl;
}

So far I've played around with a bunch of different input sets, and so far I haven't had any problems... (let me know if you test this and see anything wrong)

I highly recommend using Austin Salonen's updated answer to this question and adapting it to your language.

Answer 2

The way I thought about this was, for every index i what would be the ideal index be for selling this stock? This is of course, the index of the maximum value after i. This reduces our problem to finding the maximum element after index i for each i in [1 ... n] If we could do that in O(n) time, then we could find the best choice amongst those and report it.

A way to do this is to start traversing from the end of the array, maintaining two variables, one to save the largest element we have encountered so far max_till_now, and one to save the maximum profit we could get till now, profit. This is just so that we can do this in one pass. We could also use extra space and for each element i, store the index of the largest element in the range [i + 1 ... n] for it and then find the maximum profit.

Here's my python code:

def buyLowSellHigh(L):
    length = len(L)
    profit = 0
    max_till_now = L[length - 1]
    for i in xrange(length - 2, -1, -1):
        if L[i] > max_till_now: max_till_now = L[i]
        else:
            if max_till_now - L[i] > profit: profit = max_till_now - L[i]
    return profit

Answer 3

I'd like to describe how I approached this problem to make it easier to understand my code:

(1) For each day, if I had to sell my stock on that day, what would be the minimum amount I could have paid to buy it? Essentially, I'm keeping track of minimum price before that day

(2) For each day, if I were to sell on that day, how much am I earning? (Stock price on that day - minimum price)

This shows that I have to keep track of two things: (1) minimum stock price so far (2) best earning so far.

The problem becomes choosing which day to sell. I will sell on the day that will give me the best earning. Here is my Java code:

    public static void findBestDeal(double [] stocks) {
    double minsofar = stocks[0];
    double bestsofar = 0.0;

    for(int i=1; i< stocks.length; i++) {

        // What is the cheapest price to buy it if I'm going to sell it today
        if(stocks[i-1] < minsofar) {
            minsofar = stocks[i-1];
        }

        // How much do I earn if I sell it on ith day?
        double current_deal = stocks[i] - minsofar;

        // Is selling today better?
        if(current_deal > bestsofar) {
            bestsofar = current_deal;
        }
    }

    System.out.println("Found the best deal: " + bestsofar + " (Bought at " + minsofar + " and sold at " + (minsofar+bestsofar) + ")");

}

Answer 4

In C#:

static void Main(string[] args)
{
    double[] values = new double[7]{55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};

    double max = double.MinValue, maxDiff = double.MinValue, diff = 0;

    for (int i = 1; i < values.Length; i++)
    {
        if (values[i] > values[i - 1])
        {
            //trending upward, append to existing differential
            diff += values[i] - values[i - 1];
        }
        else
        {
            //trending downward, reset the diff
            diff = 0;
        }

        if (diff > maxDiff)
        {
            maxDiff = diff;
            max = values[i];
        }
    }

    Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);
}

EDIT: New algo based on @Joe's failing test case -- Nice Catch BTW! It's also the same answer as @Doug T's now...

static void Main(string[] args)
{
    double[] values = new double[8] { 55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24 };

    double max = double.MinValue, maxDiff = double.MinValue, diff = 0;
    double bottom = values[0];

    for (int i = 1; i < values.Length; i++)
    {
        diff += values[i] - values[i - 1];

        if (diff > maxDiff)
        {
            maxDiff = diff;
            max = values[i];
        }

        if (values[i] < bottom)
        {
            bottom = values[i];
            diff = 0;
        }
    }

    Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);
}

Answer 5

I really have to point out as an interview question expecting you to solve it as O(n) is borderline absurd. Interview questions are meant to prove you can solve a problem, which you were able to solve it. The fact you solved it in O(N^2) vs O(N) should be irrelevant. If a company would pass over hiring you for not solving this in O(N) that's probably not a company you would have wanted to work at anyway.

Answer 6

I came up with following algorithm for this problem, seems to work for all inputs. Also, If the Stock value keeps droping, the program would output not to buy this stock:

  public class GetMaxProfit 
  { 

  double minValue = -1, maxValue = -1;
  double maxDiff = 0;

  public void getProfit(double [] inputArray){
    int i=0, j=1;
    double newDiff = 0;
    while(j<inputArray.length){
         newDiff = inputArray[j]-inputArray[i];
         if(newDiff > 0){
             if(newDiff > this.maxDiff){
               this.minValue = inputArray[i];
               this.maxValue = inputArray[j];
               this.maxDiff = newDiff;
             }
        }
        else{
            i = j;
        }
        j++;
    }
 }

 public static void main(String[] args) {
    // TODO Auto-generated method stub
    GetMaxProfit obj = new GetMaxProfit();

    obj.getProfit(new double[]{55.39, 19.23, 14.29, 11.59, 10.53, 9.45, 1.24});
    if(obj.minValue != -1 && obj.maxValue != -1){
      System.out.println("Buy Value for the input: "+obj.minValue);
      System.out.println("Sell Value for the input: "+obj.maxValue);
      System.out.println("Best profit for the input: "+obj.maxDiff);
            }
            else
               System.out.println("Do Not Buy This STOCK!!);

 }

}

Is there any catch you could find in this? It's time complexity is O(N)

Answer 7

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

Answer 8

void getBestTime (int stocks[], int sz, int &buy, int &sell){
int min = 0;
int maxDiff = 0;
buy = sell = 0;
for (int i = 0; i < sz; i++) 
{
    if (stocks[i] < stocks[min])
    {
        min = i;
    }
    int diff = stocks[i] - stocks[min];
    if (diff > maxDiff) 
    {
        buy = min;
        sell = i;
        maxDiff = diff;
    }
}}

Just in case you prefer this answer. I found it in another web, but still. source:http://leetcode.com/2010/11/best-time-to-buy-and-sell-stock.html

Answer 9

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);

Answer 10

Here is my solution, same as @Doug T. except I am also keeping track of the day in an index. Please provide feedback.

 int prices[] = {4,4,5,6,2,5,1,1};
 //int prices[] = {100, 180, 260, 310, 40, 535, 695};

 int currentBestSellPrice=0;
 int currentBestBuyPrice=0;
 int lowindex=0;
 int highindex=0;
 int low=prices[0];
 int high=prices[0];
 int profit=0;
 int templowindex=0;
 for(int i=0; i< prices.length;i++)
 {
     // buy low
     if(prices[i] < low && i+1 < prices.length)
     {
         low = prices[i];  
         templowindex=i;
         high=0;
     }
     // sell high
     else if(prices[i] > high)
     {
         high = prices[i];
         int potentialprofit = (high-low);
         if(potentialprofit > profit)
         {
             profit = potentialprofit;
             currentBestSellPrice = high;
             currentBestBuyPrice = low;
             highindex=i;
             lowindex=templowindex;
         }
     }
 }


 System.out.println("Best Buy Price : "+ currentBestBuyPrice + " on day "+ lowindex);
 System.out.println("Best Sell Price : "+ currentBestSellPrice+ " on day "+ highindex );

Answer 11

F# solution for those who interested in functional take on this. I wouldn't say though it's that much different.

let start, _, profit = 
    [55.39; 109.23; 48.29; 81.59; 81.58; 105.53; 94.45; 12.24 ]
    |> Seq.fold (fun (start,newStart,profit) i -> 
                    let start = defaultArg start i
                    let newStart = defaultArg newStart i
                    let newProfit = i - newStart
                    if profit < newProfit 
                    then  Some newStart, Some newStart,newProfit
                    else if start > i 
                    then Some start, Some i, profit 
                    else Some start,Some newStart,profit) (None,None, 0.0)
printf "Best buy: %f; Best sell: %f" start.Value (start.Value + profit)

Output:

Best buy: 48.290000; Best sell: 105.530000

Answer 12

Here is my O(n) implementation for this. I am using a change array to calculate the max profit and buy and sell dates. Your comments on this are welcome.

#include<stdafx.h>
#include<stdio.h>

int main()
{
    //int arr[10] = {15, 3, 5,9,10,1,6,4,7,2};
    int arr[7] = {55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};
    int change[7];
    int n=7;
    for(int i=1;i<=n;i++)
    {
    change[i] = arr[i]- arr[i-1];
    }
    int i=0,index = 0;
    int sum = 0;
    int maxsum = 0;
    int startpos = 0;
    int endpos = 0;
    while(index < n)
    {
        sum = sum + change[index];
        if(maxsum < sum)
        {
        maxsum = sum; 
        startpos = i;
        endpos = index;

        }
        else if (sum<0) // negative number ,set sum to zero
        {
        sum = 0;
        i=index+1;
        }
        index++;
    }

    printf("max profit is%d %d %d", maxsum , startpos, endpos+1 );
}

Answer 13

This is a C solution that actually works:

void bestBuySell() { double prices[] = {10.50, 10.0, 3.0, 194.0, 55.39, 2.0, 109.23, 48.29, 81.59, 105.53, 94.45, 191.0, 200.0, 12.24}; int arrSize = 14; double bestBuy = prices[0], bestSell = prices[1], bestPotentialBuy = prices[0]; double potentialProfit = prices[1] - prices[0];

for(int i = 1; i < (arrSize-1); i++)
{
    if(prices[i] < bestBuy)
        bestPotentialBuy = prices[i];            

    if((prices[i+1] - bestPotentialBuy) > potentialProfit)
    {
        bestBuy = bestPotentialBuy;
        bestSell = prices[i+1];
        potentialProfit = prices[i+1] - bestPotentialBuy;
    }
}

printf( "bestBuy %f bestSell %f\n", bestBuy, bestSell );

}

Answer 14

In my effort to learn Go, and also to rake my brain on this one, here is my attempt.

func GetMaxProfit2(prices []float64) (float64, float64) {
    var min, max, pmin, pmax int

    for i, v := range prices {
        if v - prices[min] > prices[max] - prices[min] {
            pmax = max
            max = i
        }
        // Reset the max when min is updated.
        if v < prices[min] {
            pmin = min
            min = i
            pmax = max
            max = i
        }
    }

    // If min is ahead of max, reset the values back    
    if min >= max {
        min = pmin
        max = pmax
    }

    return prices[min], prices[max]
}

Answer 15

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
    }
}

Answer 16

Another Ruby solution:

# Here's some examples. Please feel free to give your new test.
values = [55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24]
# values = [5, 6, 4, 7, 9, 8, 8]
# values = [5, 10, 4, 6, 7]
# values = [5, 10, 4, 6, 12]
# values = [1, 2, 3, 4, 5]



# Initialize parameters.
min = values[0]
best_buy_time = values[0]
best_sell_time = values[0]
max_profit = 0



# This solution is based on comparing previous k elements and k+1 one.
# The runtime is O(n) and it only use O(1) auxiliary storage.
values.each_with_index do |value, index = 1|

  # Check value in this turn.
  puts value

  # Check current value is bigger than min or not.
  # If not, we find the new min.
  if value <= min
    min = value

  # If current value is bigger than min and
  # (value - min) is bigger than previous max_profit,
  # set new best_buy_time, best_sell_time & max_profit.
  else
    if value - min >= max_profit
      best_buy_time = min
      best_sell_time = value
      max_profit = value - min
    end

  end

end



# Let's see about the result.
puts "\nbest_buy_time: ", best_buy_time, "\nbest_sell_time: ", best_sell_time, "\nmax_profit: ", max_profit

Answer 17

what about this?

min = 100000000
max = 0

for elem in inp:
    if elem < min:
       min = elem
    tempMax = elem-min
    if tempMax > max:
        max = tempMax

print(max)

Answer 18

Here is my solution in Ruby:

values = [55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24]

max_diff = 0
diff = 0
min = values[0]
max = 0

values.each_with_index do |value, index = 1|
  # get an array of the previous values before the current one
  lag_values = values[0..index]

  # get the minimum of those previous values
  min_lag_value = lag_values.min

  # difference between current value and minimum of previous ones
  diff = values[index].to_i - min_lag_value.to_i

  # if current difference is > previous max difference, then set new values for min, max_diff, and max
  if diff > max_diff
    max_diff = diff
    min = min_lag_value
    max = values[index]
  end
end

min # => 48.29
max # => 105.3
max_diff # => 57

Cheers

Answer 19

I got 100% for the same, here you go.

public int solution(int[] A) {
      if (A == null || A.length<=1){
            return 0;
        }
        int minValue = Math.min(A[0], A[1]);
        int profit = A[1] - A[0];
        for (int i = 2; i < A.length; i++) {
          minValue = Math.min(minValue, A[i]);
          profit = Math.max(A[i] - minValue,profit);
        }

        return profit > 0 ? profit : 0;
}

Answer 20

      public void profit(float stock[], int arlen ){
            float buy = stock[0];
            float sell = stock[arlen-1];
            int bi = 0;
            int si = arlen - 1;

            for( int i = 0; i < arlen && bi < si ; i++){

                    if( stock[i] <  buy && i < si){
                            buy = stock[i];
                            bi = i;
                    }
                    if(stock[arlen - i - 1] > sell &&  (arlen - i -1)  > bi){
                            sell = stock[arlen - i - 1];
                            si = arlen - i - 1;
                    }
            }
            System.out.println(buy+" "+sell);
    }

Answer 21

Heres a javascript solution..

function getMax(arr){
        //we need more than at least 3 ints to be able to do this
        if(arr.length <= 1) return arr;
        // get the minimum price we can sell at to make a profit
        var min = arr[0];
        //get the first potential maximum profit
        var max = arr[1] - arr[0];

        //while looping through we must get a potential value, 
       //we can then compare that using the math.max using the maximum
      //and the potential prices that we have seen. Once the loop runs the ouput here should be 6!
        for(var i = 1; i < arr.length; ++i){
            var current = arr[i];
            var potential = current - min;

            max = Math.max(max, potential);
            min = Math.min(min, current);
        }

        return max;
    }

    console.log(getMax([10, 7, 5, 8, 11, 9]));

Runtime on this is O(n)

Answer 22

Solution in javascript

var stockArr = [13931, 9889, 987, 4, 89, 100];

function getBestTime(sortedArr) {
  var min = 0;
  var buyIndx = 0;
  var saleIndx = 0;
  var maxDiff = 0;
  for (var i = 0; i < stockArr.length; i++) {
    if (stockArr[i] < stockArr[min]) {
      min = i;
    }
    var diff = stockArr[i] - stockArr[min];
    if (diff > maxDiff) {
      buy = min;
      sale = i;
      maxDiff = diff;
    }
  }
  return {
    buy:buy+1,
    sale:sale+1,
    diff:maxDiff
  }
}

console.log(getBestTime(stockArr));

Answer 23

1.We cant simply take the least amount among the values as " Best Buy" and the max amount as "Best Sell" because "Sell" has to happen after "Buy".

2.We must not treat the recorded minimum as the "Best Buy" because the subsequent days may have stock values whose difference with the recorded minimum may yield profit which could be less than the "recorded profit".

3.Best Buy and Best Sell is treated as a single variant,because it is the positive difference between these values that makes max profit.

4.Since any recorded minimum in the past is a potential candidate for buying,the max profit condition must always be checked against the recorded minimum and the current day's stock price.So we always have to keep track of recorded minimum,but just the presence of recorded minimum doesn't constitute "Best Buy" because of reason number 2.

Now have the below code which executes in O(n) times will make sense.

public class BestStockBuyAndSell {

public static void main(String[] args) {

    double[] stockPrices = {55.39,109.23,48.29,81.59,105.53,94.45,12.24};
    int [] bestBuySellIndex = maxProfit(stockPrices);

    System.out.println("Best Buy At "+stockPrices[bestBuySellIndex[0]]);
    System.out.println("Best Sell At "+stockPrices[bestBuySellIndex[1]]);

    System.out.println("Max Profit = "+(stockPrices[bestBuySellIndex[1]]-stockPrices[bestBuySellIndex[0]]));

}

public static int[] maxProfit(double[] stockPrices)
{
    int bestBuy=0;
    int bestSell=0;

    int[] bestCombination ={bestBuy,bestSell};
    double recordedMinimum = stockPrices[bestBuy];
    int recordedMinimuIndex = bestBuy;
    double bestProfitSofar = stockPrices[bestSell] - stockPrices[bestBuy];

    for(int i=1;i<stockPrices.length;i++)
    {
        if(stockPrices[i] - recordedMinimum > bestProfitSofar)
        {

            bestProfitSofar = stockPrices[i] - recordedMinimum;
            bestSell = i;
            bestBuy = recordedMinimuIndex;
        }

        if(stockPrices[i] < recordedMinimum)
        {
            recordedMinimuIndex = i;
            recordedMinimum = stockPrices[i];
        }

    }

    bestCombination[0] = bestBuy;
    bestCombination[1] = bestSell;


    return bestCombination;

}

}

Answer 24

The idea is simple. Keep two pointers, lo and hi.
Do a Foor loop

1. if price is higher than hi, update hi = price, continue
2. if the price is lower than hi. Then lo and hi is one of possible candidates. Calculate the profit, store it if it's bigger than previous profits and reset lo, hi to price

def getBestProfit(prices):
    lo = hi = profit = 0


    for price in prices:
        if lo == 0 and hi == 0:
            lo = hi = price

        if price > hi:
            hi = price

        if price < low:
            tmpProfit = hi - lo
            if tmpProfit > profit:
                profit = tmpProfit

            lo = hi = price
    return profit

That's it