The famous LeetCode question #121 Understanding the Stock Buy and Sell Algorithm

Hey fellow devs! 👋 Today, let's unravel the mystery behind the famous LeetCode question #121 - Best Time to Buy and Sell Stock. Although this algorithm might seem simple once you get the hang of it, it can be a bit tricky for beginners. So, let's break it down step by step.

The Problem:

You're given an array of stock prices, where prices[i] represents the price of a stock on the ith day. Your goal? Maximize your profit by buying a stock on one day and selling it on a different day in the future. If you can't achieve any profit, return 0.

The Approach:

Imagine you're hiking across a landscape of hills and valleys. Each hill represents a day's stock price, and each valley represents a lower price. To find the highest peak (maximum profit), you'll want to follow these steps:

1. Visualize the Landscape: Think of the stock prices as a series of hills and valleys. Your goal is to find the highest peak (profit) by maximizing your uphill travels (buying low and selling high).

2. Start Trekking: As you start your hike, look for a valley (low stock price). This will be your starting point for the potential highest peak.

3. Climbing the Hill: Move forward and encounter hills (higher stock prices). Keep track of the difference between the current hill and your starting valley. This difference represents your potential profit if you sell at the current price.

4. Checking Peaks: If you encounter a hill that's higher than your previously recorded peak, update your peak to the current hill. This step ensures that you're always considering the maximum possible profit.

5. Exploring New Valleys: If you come across a valley (lower stock price) after finding a peak, make this valley your new starting point. Why? Because this valley might lead you to an even higher peak.

6. Updating Max Profit: At each step, compare your current potential profit with the previously calculated maximum profit. Keep updating it as you progress.

Putting it into Code:

This algorithm can be implemented efficiently with a single pass through the array. The trick is to find valleys (low points) and calculate the potential profit by subtracting each valley from its corresponding peak (highest point).

public int maxProfit(int[] prices) {
    int valley = prices[0];
    int maxProfit = 0;

    for (int i = 1; i < prices.length; i++) {
        if (prices[i] < valley) {
            valley = prices[i];
        } else {
            maxProfit = Math.max(maxProfit, prices[i] - valley);
        }
    }
    return maxProfit;
}

Conclusion:

While the algorithm might initially seem complex, visualizing it as a hike across hills and valleys simplifies the understanding. The key takeaway is that you're searching for valleys to find the potential highest peaks (profits). With this approach, you'll be able to conquer the challenge of maximizing your stock profits like a seasoned trader.

Keep coding and happy hiking! 🏞️🚀

If you're interested in concepts like functional programming, feel free to check out my article on Functional Programming that has garnered over 150 views! 📚👨‍💻

Happy coding! 💻🤓

LinkedIn
More Posts