Didn’t do so well on this one on the first pass.

You’re given an ordered array of prices, and are asked to find the maximum inter-day profit. Constraints: the buy must be before the sell (first price array index < second price array index), and profit is 0 if there is no positive delta.

I originally did a brute force solution that essentially came down to a double loop. Worked fine for small examples, but failed on time for long ones.

So I went and took a shower, and got half of it: if I find the minimum value, then no price after that can possibly have a bigger delta. However, it’s possible that there was a bigger delta preceding that, and I got stuck there for a while, wondering about iterating backward, but couldn’t see a definite siimple algorithm.

I got a hint that I could use a sliding window, and that gave me the right solution.

Start at index 0 as the tentative minimum.
Walk a second index forward.
If the walking index finds a new minimum, move the minimum pointer.
Otherwise, calculate the delta between the current minimum and the walking index price.
If the delta is > the old max delta, save it.

My original insight would eliminate whatever part of the array that followed the global minimum, but would have missed possible local maximum deltas (e.g., [10, 100, 1, 5] would have a true max delta of 90; scanning only after the global minimum would only have found a delta of 4). The sliding window finds that first delta of 90, and then keeps it, even though we find a new minimum at 1.

func maxProfit(prices []int) int {
    // iterate over the array from the start.
    // take the current item as the start price.
    // find the max price after this one that leads to a profit, or 0.
    // repeat for each day up to the last-1.
    // if the profit for a given iteration is > the current, save it instead.
    maxProfit := 0
    tentativeMinIndex := 0

    for i := tentativeMinIndex; i < len(prices); i++ {
        if prices[i] < prices[tentativeMinIndex] {
            tentativeMinIndex = i
            continue
        }
        // haven't moved minimum, calc profit
        thisProfit := prices[i] - prices[tentativeMinIndex]
        if thisProfit > maxProfit {
            maxProfit = thisProfit
        }
    }
    return maxProfit
}

How’d I do? Bad on the initial O(N^2) iteration, but fab on the sliding window version: top 99% in speed, top 93% in memory.

Taking a shower helped, but I won’t be able to do that in an interview, alas. (Another good argument for working at home.)

Next is palindromes, and we’ll be back to fun with Go strings again.