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

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

Approach: Single Pass (Optimal Solution)

Algorithm

1. Track the minimum price seen so far (minPrice)
2. Iterate through the array once
3. For each price, compute the potential profit (price - minPrice)
4. Update the maximum profit if the current profit is larger
5. Update minPrice if the current price is lower

Key Insight

The maximum profit is achieved by buying at the lowest price seen before the current day and selling on the current day. We only need one pass to track both the minimum price and the maximum profit.

Time & Space Complexity

• Time Complexity: O(n) - single pass through the array
• Space Complexity: O(1) - constant extra space used

Java Implementation

public class BestTimeToBuyAndSellStock {

    /**
     * Find the maximum profit from a single buy and sell transaction.
     * @param prices Array of stock prices
     * @return Maximum profit achievable, or 0 if no profit possible
     */
    public static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            // Update the minimum price seen so far
            if (price < minPrice) {
                minPrice = price;
            }
            // Calculate potential profit and update max profit
            int profit = price - minPrice;
            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }

        return maxProfit;
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        int[] prices1 = {7, 1, 5, 3, 6, 4};
        System.out.println("Input: [7,1,5,3,6,4]");
        System.out.println("Maximum profit: " + maxProfit(prices1)); // Expected: 5

        // Test case 2
        int[] prices2 = {7, 6, 4, 3, 1};
        System.out.println("Input: [7,6,4,3,1]");
        System.out.println("Maximum profit: " + maxProfit(prices2)); // Expected: 0
    }
}

Example Walkthrough

For prices = [7,1,5,3,6,4]:

1. price=7: minPrice=7, profit=0, maxProfit=0
2. price=1: minPrice=1, profit=0, maxProfit=0
3. price=5: minPrice=1, profit=4, maxProfit=4
4. price=3: minPrice=1, profit=2, maxProfit=4
5. price=6: minPrice=1, profit=5, maxProfit=5
6. price=4: minPrice=1, profit=3, maxProfit=5

Maximum profit = 5

Alternative Brute Force Approach (Less Efficient)

public static int maxProfitBruteForce(int[] prices) {
    int maxProfit = 0;
    int n = prices.length;

    // Check all buy/sell pairs
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int profit = prices[j] - prices[i];
            maxProfit = Math.max(maxProfit, profit);
        }
    }

    return maxProfit;
}

Key Insights

1. Single Pass: Achieves O(n) time complexity by tracking minimum price and max profit together
2. Buy Before Sell: The minimum price is always from a previous day, guaranteeing we buy before selling
3. Edge Case: If prices only decrease, the function returns 0 (no profitable transaction)
4. Constant Space: Uses only two variables regardless of input size

The single-pass approach is the optimal solution for this problem, providing linear time complexity with constant space usage.