leetcode month day 3: “best time to buy and sell”

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.