Longest Profitable Trade Algorithm

Question

Got this question during an interview. Wanted to know if there was a better solution:

Given a sequence of prices of a stock as [p1, p2, p3, p4, …. pN]. Trader Joe is asked to buy 1 share of the stock at time i, and sell the same share at time j. His goal is maximize the time gap between the buy time and sell time but still profitable. For example, Trade Joe is given a sequence of prices in time order:

Time,Price

10:00,10.3

10:01,10.1

10:02,11

10:03,13

10:04,9.5

10:05,7.3

10:06,8

10:07,10.2

10:08,9.8

If he buys the stock at 10:01, price = 10.1, and sells it at 10:07, price 10.2. He will make a profit of 0.1 and the time between the buy and sell would be 6 minutes. And this is the maximum time for this example.

Input

The first line contains the length of the sequence N. The next N lines contains the (time, price) pair: N Time1,price1 Time2,price2 …

Output

The maximum time between a profitable buy-then-sell pair of actions using the price sequence given

Sample input (using either a file or stdin):

7

10:01,7

10:02,4

10:03,5

10:04,10

10:05,5

10:06,2

10:07,6

Sample output:

5 (This is using a buy at 10:02 ($4) and a sell at 10:07 ($6), the time delta is 10:07 – 10:02 = 5 minutes)

The solution I proposed was O(N²), with a small optimization:

    for(int i = 0; i < lines.size(); i++){
        for(int j = lines.size()-1; j >= 0; j--){
            try
            {
                String[] partsFirst = lines.get(i).split(",");
                String[] partsLast = lines.get(j).split(",");

                String firstPriceString = partsFirst[1];
                String lastPriceString = partsLast[1];

                String firstDateString = partsFirst[0];
                String lastDateString = partsLast[0];

                double firstPriceInt = Double.parseDouble(firstPriceString);
                double lastPriceInt = Double.parseDouble(lastPriceString);


                Date date1 = format.parse(firstDateString);
                Date date2 = format.parse(lastDateString);
                long difference = date2.getTime() - date1.getTime();

                //optimization
                if(difference <= maxDuration)
                    continue;


                if(lastPriceInt > firstPriceInt && (difference) > maxDuration)
                    maxDuration = difference;
            }
            catch (ParseException ex)
            {
                System.out.println("Exception "+ex);
            }
        }
    }

Is there a more efficient solution out there?

Answer 1

Yes, there's an O(n)-time algorithm.

Scan the prices forward (beginning to end), storing in an auxiliary array the prices less than all previous prices, together with their time. Do something similar to find all prices greater than all subsequent prices. These arrays both naturally are sorted.

The optimal trade buys from the first array and sells to the second. A variant sorted merge of the two arrays will identify all O(n) trades that are profitable and maximally far apart given that one endpoint is fixed.

The way that the merge works is that we initialize an index into the "buy" (first) array and another index into the "sell" (second) array, starting at the lowest prices. If the current buy prices is less than the current sell price, then consider that trade and move on to the next highest buy price. Otherwise, move on to the next highest sell price.

Answer 2

Here's an explanation of the O(n) solution mentioned in David Eisenstat's Answer.

The main observation here is that if a point A has a lower time and a lower price than another point B, then A is a better buying point than B. For example, if you have the prices [2, 3, 4, 1, ...] (sorted by time), then there is no point in testing 3 and 4 as buying points if you already tested 2. We can conclude that, for the starting point, we only need to test the prices that are smaller than all previous prices. This could be done by scanning the prices and saving the points that match that condition.

That will give us an array buying_points = [p₁, p₂, p₃, ...]

The second observation is, for any selling point, if it's not higher in price than a buying point p_i, then it won't be higher than any previous point p_j, where j < i. This is because each element in buying points is smaller than all previous points.

Given these observations, we can construct the algorithm as follows:

We scan the buying points array and the selling points array (original prices array) backwards. For each pair of selling price and buying price:

1. If the selling price is higher, then this is a valid trade and we should check if it's better than our current best. We also go to the previous buying point since this is the best we can get for this point.
2. If the selling price is lower, we can skip that point as it won't work with any of the previous buying points.

Here's a sample code in python:

def get_max_distance(prices):
    min_price_so_far = None
    buying_points = []
    for time, price in prices:
       if min_price_so_far is None or price < min_price_so_far[1]:
           min_price_so_far = (time, price)
           buying_points.append(min_price_so_far)

    selling_points = reversed(prices)
    buying_points = reversed(buying_points)

    buying_point = next(buying_points, None)
    selling_point = next(selling_points, None)
    best = 0
    while buying_point and selling_point:
        buying_time, buying_price  = buying_point
        selling_time, selling_price = selling_point
        if selling_price > buying_price:
            if selling_time > buying_time:
                best = max(best, selling_time - buying_time)
            buying_point = next(buying_points, None)
        else:
            selling_point = next(selling_points, None)
    return best