blind-75

Best Time to Buy and Sell Stock

Best Case: The best case is when prices are in increasing order.
Worst Case: The worst case is when prices are in decreasing order.

Approach:

1. Track minimum price and maximum profit as you iterate through prices.
2. Update maximum profit whenever a new higher price is found.

Explanation to Interviewer:
“I would maintain a running minimum price and calculate potential profits at each step. This allows me to find the maximum profit with a single pass through the data.”

Code Implementation:

JavaScript:

function maxProfit(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;

    for (let price of prices) {
        if (price < minPrice) {
            minPrice = price;
        } else {
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
    }
    return maxProfit;
}

const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices)); // Output: 5

Python:

def max_profit(prices):
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        if price < min_price:
            min_price = price
        else:
            max_profit = max(max_profit, price - min_price)
    
    return max_profit

prices = [7, 1, 5, 3, 6, 4]
print(max_profit(prices))  # Output: 5