"Best Time to Buy and Sell Stock": Maximizing Profit in a Single Pass with a Greedy Approach

Today, we're diving into one of the most fundamental and frequently asked interview questions: "Best Time to Buy and Sell Stock" (LeetCode #121). This problem challenges us to find the maximum profit from a single stock transaction. While a brute-force approach might come to mind, we'll explore a highly optimized one-pass solution using a greedy strategy.

---

Understanding the Problem:

You are given an array prices, where prices[i] represents the price of a given stock on the i-th day.

Our goal is to maximize your profit by performing a single transaction: choosing one day to buy one stock and a different day in the future to sell that stock. If you cannot achieve any profit (e.g., prices only decrease), you should return 0.

Key Constraints/Rules:

• You can only complete at most one transaction (buy one, sell one).

• You must buy before you sell.

• Return 0 if no profit can be achieved.

Example:

• Input: prices = [7, 1, 5, 3, 6, 4]

• Output: 5

  • Explanation: The best strategy is to buy on day 2 (price = 1) and sell on day 5 (price = 6).

  • Profit = 6 - 1 = 5.

  • Notice that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

---

My Thought Process & Approach (One-Pass / Greedy Strategy):

A straightforward, but inefficient, approach would be to iterate through all possible buy days (i) and for each buy day, iterate through all possible sell days (j where j > i). Calculate the profit for each pair and keep track of the maximum. This would lead to an O(N^2) time complexity, which is too slow for larger inputs.

To optimize, we need a way to find the maximum profit in a single pass. This is where a greedy approach combined with a two-pointer-like idea shines.

The Core Idea: As we iterate through the prices array (representing selling days), we want to know what the lowest price seen so far has been. If we always know the minimum price available up to the current day, we can simply calculate the potential profit if we sold on the current day using that minimum buying price.

Algorithm Steps:

1. Initialize maxsum (maximum profit found so far) to 0. If no profit can be made, we return 0.

2. Initialize i (acting as our "buy day" pointer or minPriceSeen) to 0. This i will always point to the index of the lowest price encountered so far.

3. Initialize j (our "sell day" pointer) to 1. We start checking from the second day.

4. Iterate j from 1 to n-1 (the end of the prices array):

   • Check for Potential Profit: If prices[i] (our current lowest buy price) is less than prices[j] (the current day's selling price), we have a valid transaction that could yield a profit.

     • Calculate profit = prices[j] - prices[i].

     • Update maxsum = Math.max(maxsum, profit) to keep track of the best profit found.

   • Update minPrice (or i): If prices[j] (current day's price) is less than or equal to prices[i] (our current lowest buy price), it means we've found a new, even lower price. This new lower price prices[j] becomes our new ideal buying point for future transactions. So, we update i = j. We essentially "move our buy day" to this new minimum.

   • Increment j to move to the next selling day.

5. After the loop finishes, maxsum will hold the maximum profit achievable from a single transaction.

This greedy approach ensures that at each step, we're making the best possible decision to maximize profit based on the lowest buying price encountered up to that point. We don't need to look back, as the i pointer always tracks the best prior buy opportunity.

---

Java Code Implementation:

class Solution {
    public int maxProfit(int[] prices) {
        int maxsum = 0;
        int n = prices.length;
        int i = 0;
        int j = 1;
        while(j<n){
            if(prices[i]<prices[j]){
                int profit = prices[j] - prices[i];
                maxsum = Math.max(maxsum, profit);
            }else{
                i = j;
            }
            j++;
        }
        return maxsum;
    }
}

---

Time and Space Complexity Analysis:

• Time Complexity: O(N)

  • The while loop iterates exactly once for each element in the prices array (from the second element j=1 up to n-1).

  • Inside the loop, all operations (comparisons, subtraction, Math.max, pointer increments) are constant time.

  • Therefore, the total time complexity is O(N), making it highly efficient.

• Space Complexity: O(1)

  • We only use a few fixed-size integer variables (maxsum, n, i, j).

  • No auxiliary data structures are created whose size depends on the input N.

  • This makes it a highly space-efficient solution.