Leetcode 150 | Day 5: Best Time to Buy and Sell Stock - Naive vs. Optimized

Leetcode 121: Best Time to Buy and Sell Stock

Leetcode 121 asks us to determine the best time to buy and sell stock from an input array prices, where each index represents a day and the value stored at that index is the cost of stocks on that day. This problem is tagged as Dynamic Programming, but I'd argue it has a greedy element to it. The choice we need to make essentially requires the question, "If I sell today, how much profit have I made, and is that the best I could have done?" We make decisions locally at each iteration of the loop, and this leads to an optimal solution.

The problem constraints:

• You can choose to buy on any single day, and you must sell on a different day in the future.
• If it is not possible to achieve a maximum profit, you must return 0.
• 1 <= prices.length <= 10^5 - the length of our input array is capped at 100,000 indexes

• 0 <= prices[i] <= 10^4 - prices are capped at 10,000
  For both approaches we will use the following value:

- prices = [7, 1, 5, 3, 6, 4]

Approach 1: Naive (Brute Force)

The naive or brute force approach requires us to check every possible buy/sell combination in order to find the optimal set of days, resulting in an O(n²) time complexity.

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let max = 0;

    for (let i = 0; i < prices.length; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            let profit = prices[j] - prices[i];
            if (profit > max) {
                max = profit;
            }
        }
    }

    return max;
};

In our example we have 6 days, so roughly 36 checks, not a big deal. However:

• 1,000 days is approximately 1,000,000 checks
• 100,000 days is approximately 10,000,000,000 checks At that scale, the naive approach becomes impractical and results in this error.

The test results reflect this, 203 cases passed, but 9 failed. The failed cases are likely larger inputs where the number of checks becomes too costly.

---

Approach 2: Optimized (For Loop)

Tracing [7, 1, 5, 3, 6, 4]:

This approach uses two variables, minPrice and maxProfit, to track the lowest price seen so far and the best profit found so far, in one pass.

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;

    for (let i = 0; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else if (prices[i] - minPrice > maxProfit) {
            maxProfit = prices[i] - minPrice;
        }
    }

    return maxProfit;
};

Let me show you how.

We begin by initializing minPrice to Infinity. Ultimately, we want to find the day where we can purchase the stock for the lowest price, and sell for the highest price. Initializing minPrice to infinity means whatever value sits in prices[0] will be stored in minPrice on the first loop iteration. The second variable, maxProfit, is initialized to zero, since no transaction has happened yet, so there's no profit to speak of at the start.

The for loop header is standard. We initialize i to 0, we continue looping through prices while i is less than the length of prices, and we increment by 1 each time through.

Once inside the loop, we enter an if/else if condition. The if statement asks if the value at prices[i] is less than the current minPrice. If it is, we update minPrice to that value. If not, we move to the else if clause, which asks a different question:

prices[i] - minPrice > maxProfit

This equation is really asking, "if I sold today, would that beat the best profit I've found so far?"

Profit, if we sold today, is defined as:

prices[i] - minPrice

This result has three possible outcomes:

prices[i] - minPrice < maxProfit → selling today would still be worse than our current best, so we leave maxProfit untouched.
prices[i] - minPrice == maxProfit → selling today ties our current best, so there's nothing to update.
prices[i] - minPrice > maxProfit → selling today beats everything we've found so far, so this becomes our new best.

Here's a table showing the value of maxProfit at each stage of the for loop:

Whenever prices[i] - minPrice > maxProfit is true, we update maxProfit. Once the loop has gone through every day in the array, we return that final maxProfit value as the answer.

---

Conclusion

I think we have a clear winner here. While technically both approaches are valid, the naive approach times out in Leetcode, and realistically wouldn't scale well in a real world approach anyways. The optimized approach only needs to go through the array one time which leads to an O(n) time complexity, and since we aren't creating any additional data structures to solve this - space complexity is O(1).