121. Best Time to Buy and Sell Stock

Problem

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.

---

Breaking Down the Problem

At its core, this problem asks us to find two numbers in an array, buyPrice and sellPrice, such that sellPrice - buyPrice is maximized, and the index of buyPrice comes before the index of sellPrice.

Key Challenges:

1. The Time Constraint: You must buy before you sell. This means you can’t just find the minimum price and maximum price in the array; the minimum has to occur before the maximum.
2. Efficiency: How can we find the best pair without checking every single possible combination?

Edge Cases to Consider:

• An empty or single-item array: No transaction is possible, so profit is 0.
• A descending price list (e.g., [5, 4, 3, 2, 1]): No profit is possible, so the answer must be 0.

---

Intuition & Thought Process

If you were looking at a stock chart, you’d instinctively look for the lowest dip (a valley) and then the highest peak after that dip. That visual intuition is exactly what we need to model in our code.

The Brute-Force Idea (The Slow Way)

A straightforward first thought is to check every possibility.

1. Pick a day to buy.
2. Then, loop through all the following days to find the best day to sell.
3. Keep track of the biggest profit found.
4. Repeat this for every possible buy day.

This would look something like nested loops. For an array of n days, this approach would have a time complexity of O(n^2). For a small number of days, it works fine. But in an interview, with potentially thousands of days, it’s too slow and will likely time out.

---

Step-by-Step Approach (The Smart Way)

We can do much better by iterating through the prices just once. This problem is a great example of a Greedy Algorithm. At each step, we make the locally optimal choice, which leads to a globally optimal solution.

The key insight is this: as you walk through the price list, you only need to remember one thing from the past: the lowest price you’ve seen so far.

From Brute-Force to Optimized:

Instead of re-calculating for every buy day, we can maintain the lowest buy price found up to the current day. This avoids the inner loop entirely.

The Algorithm:

1. Initialize two variables: minPrice to a very large number (like infinity) and maxProfit to 0.
2. Iterate through the prices array from left to right.
3. On each day, ask two questions:
   • Is today’s price lower than minPrice? If so, we’ve found a new, better day to potentially buy. Update minPrice = currentPrice.
   • What profit would I make if I sold today? Calculate currentPrice - minPrice. If this is greater than our maxProfit, we’ve found a new best transaction. Update maxProfit with this new value.
4. After the loop finishes, maxProfit will hold the answer.

---

Time & Space Complexity

• Brute-Force Approach:
  • Time: O(n2) - because of the nested loops.
  • Space: O(1) - we only use a few variables.
• Optimized One-Pass Approach:
  • Time: O(n) - we only loop through the array once. This is a huge improvement!
  • Space: O(1) - we still only use a couple of variables.

---

Code Implementation

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = std::numeric_limits<int>::max();
        int maxProfit = 0;
        
        for (int currentPrice : prices) { 
            // Found a new, cheaper day to buy? 
            minPrice = std::min(minPrice, currentPrice); 
            // Is selling today more profitable than any previous day? 
            maxProfit = std::max(maxProfit, currentPrice - minPrice); 
        } 
        
        return maxProfit;
    }
};

class Solution {
 
    public int maxProfit(int[] prices) {
        // Start with the highest possible value for minPrice 
        int minPrice = Integer.MAX_VALUE; 
        int maxProfit = 0; 
        for (int currentPrice : prices) { 
            // Found a new, cheaper day to buy? 
            minPrice = Math.min(minPrice, currentPrice); 
            // Is selling today more profitable than any previous day? 
            maxProfit = Math.max(maxProfit, currentPrice - minPrice); 
        } 
        return maxProfit;
    }
 
}

class Solution(object):
 
    def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    min_price = float('inf')
    max_profit = 0
    
    for current_price in prices:
        min_price = min(min_price, current_price)
        max_profit = max(max_profit, current_price - min_price)
        
    return max_profit
    

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
 
    if (prices.length < 2) {
        return 0;
    }
 
    let minPrice = Infinity; // Start with the highest possible value
    let maxProfit = 0;       // The minimum possible profit is 0
 
    for(let i = 0; i < prices.length; i++) {
        if(prices[i] < minPrice) {
            minPrice = prices[i]
        } 
        
        if (prices[i] - minPrice > maxProfit) {
            maxProfit = prices[i] - minPrice; // If so, update our maximum profit
        }
    }
 
    return maxProfit
};