Buy and Sell Stock (Maximum Profit)

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.

Constraints:

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

Examples:

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.

Example 3:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.

Approach 1: One Pass (Optimal)

Algorithm:

1. Keep track of the minimum price seen so far
2. For each day, calculate the profit if we sell on that day
3. Update the maximum profit found so far

Time Complexity: O(n)
Space Complexity: O(1)

Python:

def maxProfit(prices):
    """
    Find maximum profit from buying and selling stock
    Time: O(n)
    Space: O(1)
    """
    if not prices:
        return 0
    
    min_price = prices[0]
    max_profit = 0
    
    for price in prices[1:]:
        # Update minimum price seen so far
        min_price = min(min_price, price)
        
        # Calculate profit if we sell today
        profit = price - min_price
        
        # Update maximum profit
        max_profit = max(max_profit, profit)
    
    return max_profit

Java:

class Solution {
    /**
     * Find maximum profit from buying and selling stock
     * Time: O(n)
     * Space: O(1)
     */
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        
        int minPrice = prices[0];
        int maxProfit = 0;
        
        for (int i = 1; i < prices.length; i++) {
            // Update minimum price seen so far
            minPrice = Math.min(minPrice, prices[i]);
            
            // Calculate profit if we sell today
            int profit = prices[i] - minPrice;
            
            // Update maximum profit
            maxProfit = Math.max(maxProfit, profit);
        }
        
        return maxProfit;
    }
}

Go:

// maxProfit - Find maximum profit from buying and selling stock
// Time: O(n)
// Space: O(1)
func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    
    minPrice := prices[0]
    maxProfit := 0
    
    for i := 1; i < len(prices); i++ {
        // Update minimum price seen so far
        if prices[i] < minPrice {
            minPrice = prices[i]
        }
        
        // Calculate profit if we sell today
        profit := prices[i] - minPrice
        
        // Update maximum profit
        if profit > maxProfit {
            maxProfit = profit
        }
    }
    
    return maxProfit
}

JavaScript:

/**
 * Find maximum profit from buying and selling stock
 * Time: O(n)
 * Space: O(1)
 */
function maxProfit(prices) {
    if (prices.length === 0) {
        return 0;
    }
    
    let minPrice = prices[0];
    let maxProfit = 0;
    
    for (let i = 1; i < prices.length; i++) {
        // Update minimum price seen so far
        minPrice = Math.min(minPrice, prices[i]);
        
        // Calculate profit if we sell today
        const profit = prices[i] - minPrice;
        
        // Update maximum profit
        maxProfit = Math.max(maxProfit, profit);
    }
    
    return maxProfit;
}

C#:

public class Solution {
    /// <summary>
    /// Find maximum profit from buying and selling stock
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int MaxProfit(int[] prices) {
        if (prices.Length == 0) {
            return 0;
        }
        
        int minPrice = prices[0];
        int maxProfit = 0;
        
        for (int i = 1; i < prices.Length; i++) {
            // Update minimum price seen so far
            minPrice = Math.Min(minPrice, prices[i]);
            
            // Calculate profit if we sell today
            int profit = prices[i] - minPrice;
            
            // Update maximum profit
            maxProfit = Math.Max(maxProfit, profit);
        }
        
        return maxProfit;
    }
}

Approach 2: Brute Force

Algorithm:

1. For each day, consider it as a buy day
2. For each subsequent day, consider it as a sell day
3. Calculate profit and keep track of maximum

Time Complexity: O(n²)
Space Complexity: O(1)

Python:

def maxProfit(prices):
    """
    Find maximum profit using brute force approach
    Time: O(n²)
    Space: O(1)
    """
    max_profit = 0
    
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            profit = prices[j] - prices[i]
            max_profit = max(max_profit, profit)
    
    return max_profit

Java:

class Solution {
    /**
     * Find maximum profit using brute force approach
     * Time: O(n²)
     * Space: O(1)
     */
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                maxProfit = Math.max(maxProfit, profit);
            }
        }
        
        return maxProfit;
    }
}

Go:

// maxProfit - Find maximum profit using brute force approach
// Time: O(n²)
// Space: O(1)
func maxProfit(prices []int) int {
    maxProfit := 0
    
    for i := 0; i < len(prices); i++ {
        for j := i + 1; j < len(prices); j++ {
            profit := prices[j] - prices[i]
            if profit > maxProfit {
                maxProfit = profit
            }
        }
    }
    
    return maxProfit
}

JavaScript:

/**
 * Find maximum profit using brute force approach
 * Time: O(n²)
 * Space: O(1)
 */
function maxProfit(prices) {
    let maxProfit = 0;
    
    for (let i = 0; i < prices.length; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            const profit = prices[j] - prices[i];
            maxProfit = Math.max(maxProfit, profit);
        }
    }
    
    return maxProfit;
}

C#:

public class Solution {
    /// <summary>
    /// Find maximum profit using brute force approach
    /// Time: O(n²)
    /// Space: O(1)
    /// </summary>
    public int MaxProfit(int[] prices) {
        int maxProfit = 0;
        
        for (int i = 0; i < prices.Length; i++) {
            for (int j = i + 1; j < prices.Length; j++) {
                int profit = prices[j] - prices[i];
                maxProfit = Math.Max(maxProfit, profit);
            }
        }
        
        return maxProfit;
    }
}

Approach 3: Dynamic Programming

Algorithm:

1. Use DP to track the minimum price and maximum profit
2. For each day, decide whether to buy or sell

Time Complexity: O(n)
Space Complexity: O(1)

Python:

def maxProfit(prices):
    """
    Find maximum profit using dynamic programming approach
    Time: O(n)
    Space: O(1)
    """
    if not prices:
        return 0
    
    # DP state: min_price and max_profit
    min_price = prices[0]
    max_profit = 0
    
    for i in range(1, len(prices)):
        # Update minimum price (buy decision)
        min_price = min(min_price, prices[i])
        
        # Update maximum profit (sell decision)
        max_profit = max(max_profit, prices[i] - min_price)
    
    return max_profit

Java:

class Solution {
    /**
     * Find maximum profit using dynamic programming approach
     * Time: O(n)
     * Space: O(1)
     */
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        
        // DP state: minPrice and maxProfit
        int minPrice = prices[0];
        int maxProfit = 0;
        
        for (int i = 1; i < prices.length; i++) {
            // Update minimum price (buy decision)
            minPrice = Math.min(minPrice, prices[i]);
            
            // Update maximum profit (sell decision)
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
        
        return maxProfit;
    }
}

Go:

// maxProfit - Find maximum profit using dynamic programming approach
// Time: O(n)
// Space: O(1)
func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    
    // DP state: minPrice and maxProfit
    minPrice := prices[0]
    maxProfit := 0
    
    for i := 1; i < len(prices); i++ {
        // Update minimum price (buy decision)
        if prices[i] < minPrice {
            minPrice = prices[i]
        }
        
        // Update maximum profit (sell decision)
        profit := prices[i] - minPrice
        if profit > maxProfit {
            maxProfit = profit
        }
    }
    
    return maxProfit
}

JavaScript:

/**
 * Find maximum profit using dynamic programming approach
 * Time: O(n)
 * Space: O(1)
 */
function maxProfit(prices) {
    if (prices.length === 0) {
        return 0;
    }
    
    // DP state: minPrice and maxProfit
    let minPrice = prices[0];
    let maxProfit = 0;
    
    for (let i = 1; i < prices.length; i++) {
        // Update minimum price (buy decision)
        minPrice = Math.min(minPrice, prices[i]);
        
        // Update maximum profit (sell decision)
        maxProfit = Math.max(maxProfit, prices[i] - minPrice);
    }
    
    return maxProfit;
}

C#:

public class Solution {
    /// <summary>
    /// Find maximum profit using dynamic programming approach
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int MaxProfit(int[] prices) {
        if (prices.Length == 0) {
            return 0;
        }
        
        // DP state: minPrice and maxProfit
        int minPrice = prices[0];
        int maxProfit = 0;
        
        for (int i = 1; i < prices.Length; i++) {
            // Update minimum price (buy decision)
            minPrice = Math.Min(minPrice, prices[i]);
            
            // Update maximum profit (sell decision)
            maxProfit = Math.Max(maxProfit, prices[i] - minPrice);
        }
        
        return maxProfit;
    }
}

Key Insights

1. Greedy Approach: At each day, we make the locally optimal choice (buy at minimum price, sell at current price).
2. Single Pass: We only need to traverse the array once, keeping track of the minimum price and maximum profit.
3. Dynamic Programming: The problem has optimal substructure - the maximum profit up to day i depends on the minimum price up to day i.
4. No Need for Complex State: We only need to track two variables: minimum price and maximum profit.

Edge Cases

• Empty array: [] → result is 0
• Single element: [5] → result is 0 (can't sell)
• Decreasing prices: [7,6,4,3,1] → result is 0
• Increasing prices: [1,2,3,4,5] → result is 4
• Same prices: [5,5,5,5] → result is 0

Test Cases

# Test case 1: Normal case
assert maxProfit([7,1,5,3,6,4]) == 5

# Test case 2: No profit possible
assert maxProfit([7,6,4,3,1]) == 0

# Test case 3: Increasing prices
assert maxProfit([1,2,3,4,5]) == 4

# Test case 4: Single element
assert maxProfit([5]) == 0

# Test case 5: Two elements
assert maxProfit([1,2]) == 1
assert maxProfit([2,1]) == 0

Follow-up Questions

1. Best Time to Buy and Sell Stock II: You can complete as many transactions as you like (buy one and sell one share of the stock multiple times).
2. Best Time to Buy and Sell Stock III: You may complete at most two transactions.
3. Best Time to Buy and Sell Stock IV: You may complete at most k transactions.
4. Best Time to Buy and Sell Stock with Cooldown: After selling, you cannot buy on the next day.
5. Best Time to Buy and Sell Stock with Transaction Fee: Each transaction has a fee.

Common Mistakes

1. Not handling empty array: Forgetting to check for empty input.
2. Incorrect profit calculation: Not considering that we must buy before selling.
3. Off-by-one errors: Incorrect loop bounds or array indexing.
4. Not updating minimum price: Forgetting to update the minimum price at each step.

Trade-offs

• One Pass vs Brute Force: One pass is optimal, brute force is easier to understand
• Space Complexity: All approaches use O(1) space
• Time Complexity: One pass is O(n), brute force is O(n²)
• Readability: One pass is more efficient but requires understanding of the greedy approach