Best Time to Buy and Sell Stock - LeetCode Solution in C++, Java, Python

1. Introduction

The "Best Time to Buy and Sell Stock" problem involves finding the maximum profit that can be achieved by buying and selling a single stock on different days. It's a common problem to test understanding of array traversal and finding the maximum difference in an efficient manner.

2. 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 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.

3. Solution in C++

int maxProfit(vector<int>& prices) {
    int maxProfit = 0;
    int minPrice = INT_MAX;

    for (int price : prices) {
        minPrice = min(minPrice, price);
        maxProfit = max(maxProfit, price - minPrice);
    }

    return maxProfit;
}

Explanation:

1. Initialize maxProfit as 0 and minPrice as the maximum possible integer value.

2. Traverse the prices array.

3. Update minPrice to the minimum value found so far.

4. Calculate the profit for each day (price - minPrice) and update maxProfit if it's higher.

5. The value of maxProfit at the end of the array traversal is the maximum profit achievable.

4. Solution in Java

public int maxProfit(int[] prices) {
    int maxProfit = 0;
    int minPrice = Integer.MAX_VALUE;

    for (int price : prices) {
        minPrice = Math.min(minPrice, price);
        maxProfit = Math.max(maxProfit, price - minPrice);
    }

    return maxProfit;
}

Explanation:

1. Initialize maxProfit to 0 and minPrice to the maximum integer value.

2. Iterate over each price in prices.

3. Keep track of the minimum price seen so far.

4. For each day, calculate the potential profit and update maxProfit if the current profit is higher.

5. The final maxProfit is the maximum profit that can be achieved.

5. Solution in Python

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

    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)

    return max_profit

Explanation:

1. Initialize max_profit as 0 and min_price as infinity.

2. Loop through each price in prices.

3. Update min_price to be the lowest price encountered so far.

4. Calculate the profit for selling at the current price and update max_profit if it's greater.

5. The final value of max_profit represents the maximum possible profit.