121. Best Time to Buy and Sell Stock(Java, Easy, O(n))

• LeetCode 121: Best Time to Buy and Sell Stock

Problem Statement

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.

Solution Approach

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price: prices) {
            // buy low sell high
            if (price < minPrice) {
                minPrice = price;
            } 
            else if ((price - minPrice) > maxProfit) {
                // you won't want to update profit when price is lower
                maxProfit = price - minPrice;
            }
        }
        return maxProfit;
    }
}

Algorithm Explanation

Core Strategy: One-Pass Tracking

The algorithm uses a single pass through the array to track two key values:

1. Minimum price seen so far (minPrice) - potential buying point
2. Maximum profit possible (maxProfit) - best profit achievable

Step-by-Step Logic

Step 1: Initialize Variables

int minPrice = Integer.MAX_VALUE;  // Track lowest price seen
int maxProfit = 0;                // Track best profit so far

Step 2: Process Each Price

For each price in the array, we have two scenarios:

Scenario A: New Minimum Price Found

if (price < minPrice) {
    minPrice = price;  // Update potential buying point
}

• When we find a lower price, it becomes our new potential buying point
• All future selling opportunities will be calculated against this new minimum

Scenario B: Potential Selling Opportunity

else if ((price - minPrice) > maxProfit) {
    maxProfit = price - minPrice;  // Update best profit
}

• If current price isn't a new minimum, check if selling today would give better profit
• Only update if this profit exceeds our current best

Visual Example

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

Day:    0  1  2  3  4  5
Price:  7  1  5  3  6  4
        ↓  ↓  ↓  ↓  ↓  ↓

Trace Through Algorithm:

Result: Maximum profit = 5 (buy at price 1, sell at price 6)

Key Insights

1. Why This Works

• Maintains chronological order: We only consider selling after buying
• Optimal substructure: At each point, we know the best profit possible up to that day
• Greedy approach: Always keep track of the lowest buying price for future opportunities

2. Why We Don't Need to Track Selling Price

// We don't need to store the actual selling price
// because we only care about the maximum profit value

3. Edge Cases Handled

• No profit possible: Returns 0 (initial value)
• Single day: No transaction possible, returns 0
• Decreasing prices: minPrice keeps updating, maxProfit stays 0

Complexity Analysis

Time Complexity: O(n)

• Single pass through the array
• Constant time operations for each element

Space Complexity: O(1)

• Only uses two extra variables regardless of input size
• No additional data structures needed

Alternative Approaches Comparison

Common Mistakes to Avoid

1. Calculating profit with future minimum:

   // ❌ Wrong: This violates chronological order
   maxProfit = futureMaxPrice - currentMinPrice;
   

2. Tracking unnecessary state:

   // ❌ Unnecessary: Don't need to track max price
   int maxPrice = 0;  // Not needed for this problem
   

3. Not handling decreasing array:

   // ✅ Correct: Algorithm naturally handles this case
   // If prices only decrease, maxProfit remains 0
   

Test Cases

// Example 1: Normal case
prices = [7,1,5,3,6,4] → Output: 5

// Example 2: No profit possible  
prices = [7,6,4,3,1] → Output: 0

// Example 3: Maximum at end
prices = [1,2,3,4,5] → Output: 4

// Example 4: Single element
prices = [1] → Output: 0

Conclusion

This solution elegantly solves the stock trading problem by:

• Tracking the minimum buying price as we scan left to right
• Calculating potential profit at each selling opportunity
• Maintaining the maximum profit seen so far

The beauty of this approach is its simplicity and efficiency - it naturally respects the time constraint (buy before sell) while finding the optimal solution in a single pass.