Blind 75.02 - Best Time to Buy and Sell Stock

Best time to buy and sell stock.

Problem description

Taken directly from LeetCode.

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= \(10^5\)
• 0 <= prices[i] <= \(10^4\)

Solution type

Caching. Maybe counts as greedy too? But it’s not really a greedy algorithm so much as “you’re supposed to maximize this one value”.

Solution

I think I’ve done this one a few times before, although it takes me a bit to remember the logic behind the optimal solution. Took <5 minutes.

int maxProfit(vector<int>& prices) {
    int minSoFar = prices[0], bestProfit = 0;
    for (int currentPrice : prices) {
        minSoFar = currentPrice < minSoFar ? currentPrice : minSoFar;
        bestProfit = currentPrice - minSoFar > bestProfit ? currentPrice - minSoFar : bestProfit; 
    }
    return bestProfit;
}

\(O(n)\) time, \(O(1)\) space.

This is how I view it: if I’m selling on day i, what would have been the best price to buy the stock? The answer is: the minimum price in the first i days that came before the ith day. My goal is to answer this question for every day represented in the data, then pick the maximum profit from all of those days. To me, this intuitively becomes a one-pass for loop where I’m doing the same sequence of operations on each element.

Like with two sum, you can do an \(O(n^2)\) loop that checks every element that came before the current element, and you can compute \(O(n)\) possible profits for the current selling price. Basically, do an \(O(n)\) operation \(O(n)\) times. But buying cheaper is always the better option, so you only need to cache the minimum to get the optimal solution. This makes it an \(O(1)\) operation \(O(n)\) times. Keeping a minSoFar variable up to date nets you an \(O(n)\) time solution in \(O(1)\) space.

I guess you can cache the maxSoFar and skip selling that are greater than minSoFar but less than the highest selling price you’ve seen since minSoFar; however, I think that makes the code a lot more confusing without improving time complexity. Heck, it might be slower - you need to check another conditional every time, and if you meet the condition then you only skip one arithmetic computation.

Yes, I abuse ternary operators in interview problems. It’s just faster. Hehehe.