Single sell best profit: finding the best price difference between two days in an array of stock values

Receiving an invitation to be interviewed by a fortune 50 (fifty) company located 11,000+ kilometers away can turn an average day of a software developer into an exciting one. Especially, if it's one of those companies that everybody knows, unless they've been living under a rock.

An online coding exercise and a phone conversation after, I received a confirmation, along with my flight itinerary and a hotel booking – all organized for me on a short notice, which I thought was a nice gesture on their behalf. Indeed, everyone involved was really polite and made an excellent impression. I wish this hadn't coincided with one of my busiest times in the year, being assigned to a major project one week before it was due, with only one day to get up to speed and deliver a functional authentication module. Thankfully, that wasn't much of a challenge, and I used whatever time I could find to prepare.

There were 4 interviews, with 4 professionals in total. Some general questions, which didn't allow me to talk much about my experience, and technical exercises in the style of Silicon Valley: here's the problem, how would you solve it to perform in O(N) time?

I've done my share of real life diverse and fairly complex algorithms, as having an intuitive affinity for performance and clever code can make it satisfying as hell to see 2 gigabytes of data processed in less than a second on an average computer, for instance. When something's not fast enough, I just create my version of it, if I can get away with it. The C# code highlighter, for instance, used for coloring the actual examples below was completely written from scratch, including the lexer, when I couldn't find an accurate and fast highlighter that produced the results I needed.

The first three vis-a-vis meetings were a delight. The fourth one consisted of a rather brief introduction (or a lack of) and a rather abrupt transition to a coding challenge. Writing parsers, approximate search engines, image filters and serializers at a leisurely pace is one thing. Standing at the whiteboard, having to start narratively working to arrive at a solution, with little time to gather thoughts and a rather unsympathetic examinator is not quite the same. A little reminiscent of school days, but that was more than a half life ago.

It was later revealed, by virtue of reciprocal questions, that the interviewer was someone who, to paraphrase, solves problems that no one else can. FTL immediately sprung to mind, along with string theory, cancer cure, Baryon Asymmetry, revealing the events before the Planck Epoch... At the very least, it should be a patented way to calculate prime numbers. But I digress.

The problem – finding the lowest stock price to buy at and the highest to sell at

Given an array of a certain length, with the indexes corresponding to days and values – to average stock prices, find two days that would yield the biggest profit.

So, clearly, we must buy on one day and find another to sell. Easy enough? It is, until you start thinking about how to solve it in the most efficient way. Despite starting on the right track, I ended up going down a O(N^2) path, narrating over my incomplete solution hastily scribbled on the board. When asked if there's an O(N) method, I couldn't see one fast enough to answer. It's a tough balance between interview preparations, meeting the deadline and getting enough rest to last through 4 sessions on an empty stomach. Something in that equation didn't quite work in favor of a clear head.

What's the solution already?

Ok, ok. All I needed was to sit down and gather my thoughts. Something like this should be as simple as 5*5. Not sure why it trips up so many people.

The O(N) time solution with O(1) space complexity is simpler than anything else. So, let's talk through it (where's my whiteboard):

• What makes this harder than a simple min-max problem is time. Time is directional. From left to right. We need to buy low first. Sell high later. This is the core of the problem.
• We're interested in the biggest difference that's calculated by subtracting a value with a lower array index from another with a higher index. So this is a constraint.
  So our Xmax=a[m]-a[n], where m>n and a[m] > a[n]. Think about it.
• We also need to scan the whole array. All elements. Otherwise there can be no confidence that the best pair has been found.
• We can search backwards or forward. But let's do so from the end of the array.
• If we have only one element in the array, then this is the best buy/sell option, as no others are present. The final result should only include positive values, otherwise be undefined. But in the calculation phase, this is fine. So, on the first iteration, our min = a[len-1] and max = a[len-1]. This is logically sound. So far so good. Logic is what we're looking for. This is memorized in local variables, together with the indexes, as the best results found thus far.
• Let's say that the array now has two elements. If the difference with the new value is larger than previously (it was 0), then update the min index to point to this value.
  On the other hand, if the figure is greater than its sibling, then we want to take a note of it. Introducing another variable to remember this larger maximum, while keeping the original proven maximum intact.
• Now let's have 3 elements. If the second one was smaller, then we updated the minimum index to that. If the third one is smaller, we'll do the same.
  If the second one was larger, then we noted it in a variable. Now, if the third value is smaller than the potential maximum, calculating their difference will help determine whether two better values have been found. If that's the case – upgrade the potential maximum to actual maximum and update the minimum.
• Rinse-repeat.

What if the new minimum is larger than the original minimum? Doesn't matter! If the difference is larger – that's what we're looking for!

We only update the potential maximum if a larger value than the original maximum has been found. Otherwise – it'll always be the initial element, as in the case of: 1,2,3,4,5.
The minimum is updated every time that the difference with the potential maximum is larger than the original difference. If each value decreases when going backwards, as in the example above, it'll happen on each cycle. However, if the sequence is inverted, the minimum will never be updated. Thus, no good time to buy/sell would be found.

The algorithm:

public BestProfit FindMaximumProfit(double[] input)
{
    if (input == null)
        return null; //or throw a null argument exception

    int i = input.Length;

    int bestMinIndex = i - 1;
    int bestMaxIndex = i - 1;

    double candidateMaxValue = 0;
    int candidateMaxIndex = 0;

    double bestDifference = 0;
    double difference = 0;

    while (--i >= 0)
    {
        if (input[i] > candidateMaxValue) {
            candidateMaxValue = input[i];
            candidateMaxIndex = i;
        }

        difference = candidateMaxValue - input[i];

        if (difference > bestDifference)
        {
            bestDifference = difference;
            bestMinIndex = i;
            bestMaxIndex = candidateMaxIndex;
        }
    }

    if(bestMaxIndex != bestMinIndex)
        return new BestProfit(bestMinIndex, bestMaxIndex, input[bestMinIndex], input[bestMaxIndex]);

    return null;
}

public class BestProfit
{
    public int BuyIndex { get; set; }
    public int SellIndex { get; set; }
    public double BuyPrice { get; set; }
    public double SellPrice { get; set; }

    public BestProfit(int buyIndex, int sellIndex, double buyPrice, double sellPrice)
    {
        BuyIndex = buyIndex;
        SellIndex = sellIndex;
        BuyPrice = buyPrice;
        SellPrice = sellPrice;
    }
}