121. Best Time to Buy and Sell Stock

Intitution

To maximize profit, we want to buy at the lowest price and sell at the highest price after buying. So, while iterating through the array, we keep track of the minimum price seen so far, and at each step, calculate the profit if we sell at the current price. The answer will be the maximum of all such profits.

Complxity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(n)$

Code

public int maxProfit(int[] prices) {
    
    // Initialize the minimum price to the first day's price
    int minPriceSoFar = prices[0];
    
    // Initialize profit to 0 (no transaction yet)
    int maxProfit = 0;

    // Traverse the price array starting from the second day
    for (int i = 1; i < prices.length; ++i) {
        
        // Calculate the profit if sold today, and update maxProfit
        maxProfit = Math.max(prices[i] - minPriceSoFar, maxProfit);
        
        // Update the minimum price so far if today's price is lower
        minPriceSoFar = Math.min(prices[i], minPriceSoFar);
    }

    // Return the maximum profit found
    return maxProfit;
}