Leetcode - Best Time to Buy and Sell Stock Solution

Finding the best time to buy and sell stock sounds like a finance problem, but it's actually a great algorithm challenge. The problem asks us to find the maximum profit from buying on one day and selling on a different day in the future. My first solution checked all possible pairs, which was O(n²). But by tracking just the minimum price seen so far, I reduced it to O(n).

The key insight is that we should always try to buy at the lowest price we've encountered, and sell at the current price if it gives us a better profit. We don't need to check all pairs because we're always buying at the best possible price.

The Problem

You're given an array prices where prices[i] is the stock price on day i. The goal is to maximize profit by buying stock on one day and selling it on a different day in the future. Sounds straightforward, right? Well, my first attempt wasn't as efficient as it could be.

My First Attempt

My initial thought was: "I need to check every possible pair of buy and sell days." So I wrote a solution with two nested loops:

function maxProfitNaive(prices) {
  let maxProfit = 0;

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

  return maxProfit;
}

This worked, but I quickly realized it had a time complexity of O(n²). For large arrays, this would be slow. I knew there had to be a better way.

The Aha Moment

I started thinking: "What if I track the minimum price I've seen so far, and calculate profit based on that?" This way, I only need one pass through the array. The key insight was that I should always try to buy at the lowest price I've encountered, and sell at the current price if it gives me a better profit.

Here's what I came up with:

function maxProfit(prices) {
  let minPrice = Infinity; // Track the lowest price seen so far
  let maxProfit = 0; // Track the maximum profit found

  for (let i = 0; i < prices.length; i++) {
    // If current price is lower, update our minimum
    if (prices[i] < minPrice) {
      minPrice = prices[i];
    }
    // Otherwise, check if selling now gives better profit
    else if (prices[i] - minPrice > maxProfit) {
      maxProfit = prices[i] - minPrice;
    }
  }

  return maxProfit;
}

Why This Works

The algorithm works because:

• We only need to remember the minimum price we've seen
• At each step, we check if selling at the current price (after buying at the minimum) gives us a better profit
• We don't need to check all pairs because we're always buying at the best possible price (the minimum so far)

Testing It Out

Let me test it with an example:

const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices)); // Output: 5

Here's what happens:

• Day 0: price is 7, minPrice becomes 7, profit is 0
• Day 1: price is 1, minPrice becomes 1 (lower!), profit is still 0
• Day 2: price is 5, minPrice is 1, profit = 5 - 1 = 4
• Day 3: price is 3, minPrice is 1, profit = 3 - 1 = 2 (not better)
• Day 4: price is 6, minPrice is 1, profit = 6 - 1 = 5 (better!)
• Day 5: price is 4, minPrice is 1, profit = 4 - 1 = 3 (not better)

So the answer is 5, which is correct!

Java Version

I also implemented it in Java, which follows the same logic:

public class StockProfit {
    public static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int 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;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(prices)); // Output: 5
    }
}

What I Learned

This problem taught me that sometimes the most intuitive solution (checking all pairs) isn't the most efficient. By thinking about what information I actually need to track (just the minimum price and maximum profit), I reduced the time complexity from O(n²) to O(n).

The key takeaway? Always ask yourself: "What's the minimum information I need to solve this?" Often, the answer leads to a more efficient solution.

Key Takeaways

• Don't jump to nested loops immediately. Think about what you're actually tracking.
• Sometimes one pass is enough if you maintain the right state
• The space complexity is O(1). We only use a couple of variables.
• This pattern of tracking a minimum/maximum while iterating is useful in many problems

I hope this helps you the next time you encounter a similar problem. Happy coding!