12. Best Time to Buy and Sell Stock

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. If you cannot achieve any profit, return 0.

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.

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: No profitable transaction is possible.

Problem Breakdown:

1. Track the minimum price seen so far and the maximum profit. Initialize minPrice to the first element and maxProfit to 0.

• minPrice = prices[0]
  maxProfit = 0

2. Iterate through prices starting from day 2. For each price, check if it is a new minimum buying opportunity.

• for price in prices[1:]:
      if price < minPrice:
          minPrice = price

3. Calculate the profit if we sold at the current price and update maxProfit if this profit is better.

•     profit = price - minPrice
      maxProfit = max(maxProfit, profit)

4. After iterating all prices, return the maximum profit found. If no profit is possible, it remains 0.

• return maxProfit

Summary:

Maintain a running minimum price and maximum profit. For each day, check if today offers a lower buy price or a higher sell profit. This greedy approach ensures we always consider the best buy before the current sell day.

Time and Space Complexity:

Time Complexity: O(n) - single pass through the prices array.

Space Complexity: O(1) - only two variables used.

Python Solution:

def maxProfit(prices):
    minPrice = prices[0]
    maxProfit = 0
    for price in prices[1:]:
        if price < minPrice:
            minPrice = price
        profit = price - minPrice
        maxProfit = max(maxProfit, profit)
    return maxProfit

JavaScript Solution:

var maxProfit = function(prices) {
    let minPrice = prices[0];
    let maxProfit = 0;
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] < minPrice) minPrice = prices[i];
        const profit = prices[i] - minPrice;
        maxProfit = Math.max(maxProfit, profit);
    }
    return maxProfit;
};

Java Solution:

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