Best time to buy and Sell stock

Problem Statement

Given an array of stock prices where prices[i] is the price on day i, find the maximum profit you can achieve from one transaction (buy one and sell one share). You must buy before you sell.

Example:

• Input: [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

Approach 1: Brute Force

Intuition

For each day, consider buying on that day and selling on every future day. Track the maximum profit.

Algorithm

1. For each day i (buying day)
2. For each day j > i (selling day)
3. Calculate profit = prices[j] - prices[i]
4. Track maximum profit

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

Complexity Analysis

• Time Complexity: O(n²) - Checking all pairs of days
• Space Complexity: O(1) - No extra space used

Approach 2: Single Pass (Optimal)

Intuition

To maximize profit, we want to buy at the lowest price and sell at the highest price after that. As we traverse, we track the minimum price seen so far and calculate the potential profit at each step.

Algorithm

1. Initialize minPrice to infinity and maxProfit to 0
2. For each price:
   • Update minPrice if current price is lower
   • Calculate profit if we sell today: price - minPrice
   • Update maxProfit if this profit is higher
3. Return maxProfit

public class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        
        for (int price : prices) {
            // Update minimum price seen so far
            minPrice = Math.min(minPrice, price);
            
            // Calculate profit if we sell today
            int profit = price - minPrice;
            
            // Update maximum profit
            maxProfit = Math.max(maxProfit, profit);
        }
        
        return maxProfit;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass through the array
• Space Complexity: O(1) - Only two variables used

Visual Example

For array [7, 1, 5, 3, 6, 4]:

Alternative: Kadane's Algorithm Perspective

This problem can be transformed into finding maximum subarray sum of daily differences.

Key Takeaways

1. Track the minimum while iterating - Classic single-pass optimization pattern
2. The problem is essentially: find max(prices[j] - prices[i]) where j > i
3. Greedy approach works because we always want to buy at the lowest point before selling
4. If no profit is possible (prices only decrease), return 0
5. This is a foundation for more complex stock problems (multiple transactions, cooldown, etc.)
6. Connection to Kadane's: Sum of daily differences equals total price change