Best Time to Buy and Sell Stock: Maximize Profit with Efficient Algorithms

The Best Time to Buy and Sell Stock problem is a fundamental challenge in algorithmic trading and a staple on LeetCode. The objective is to determine the maximum profit achievable from a single buy-sell transaction. This guide covers both the brute force and optimal approaches in Java and Python, including complexity analysis and key insights.

Problem Statement

You are given an array prices where prices[i] represents the price of a stock on day i. The goal is to determine the maximum profit from buying on one day and selling on a later day. If no profit is possible, return 0.

Examples:

Example 1:  
Input: prices = [7,1,5,3,6,4]  
Output: 5  
Explanation: Buy on day 2 (price = 1), sell on day 5 (price = 6).  

Example 2:  
Input: prices = [7,6,4,3,1]  
Output: 0  
Explanation: Prices keep decreasing; no profitable transaction possible.  

Constraints:

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

Approach 1: Brute Force (O(n²))

Intuition

Compare every possible buy-sell pair (i, j) where i < j and compute prices[j] - prices[i], tracking the maximum profit.

Drawbacks

• Inefficient for large datasets (100,000 elements).
• Time complexity of O(n²) makes it impractical for large inputs.

Java Code

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++) {  
            maxProfit = Math.max(maxProfit, prices[j] - prices[i]);  
        }  
    }  
    return maxProfit;  
}  

Python Code

def maxProfit(prices):  
    max_profit = 0  
    for i in range(len(prices)):  
        for j in range(i+1, len(prices)):  
            max_profit = max(max_profit, prices[j] - prices[i])  
    return max_profit  

Approach 2: Optimized One-Pass Solution (O(n))

Intuition

Instead of checking every pair, maintain two variables:

1. minPrice – Tracks the lowest price encountered so far.
2. maxProfit – Tracks the highest profit seen so far.

Why This Works

• Uses a single pass over the array.
• Achieves O(n) time complexity, making it ideal for large datasets.

Step-by-Step Example

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

Java Code

public int maxProfit(int[] prices) {  
    int minPrice = Integer.MAX_VALUE;  
    int maxProfit = 0;  
    for (int price : prices) {  
        if (price < minPrice) {  
            minPrice = price;  
        } else {  
            maxProfit = Math.max(maxProfit, price - minPrice);  
        }  
    }  
    return maxProfit;  
}  

Python Code

def maxProfit(prices):  
    min_price = float('inf')  
    max_profit = 0  
    for price in prices:  
        min_price = min(min_price, price)  
        max_profit = max(max_profit, price - min_price)  
    return max_profit  

Complexity Analysis

• Time Complexity: O(n) – Single pass through the array.
• Space Complexity: O(1) – Uses only two variables (minPrice, maxProfit).

Key Takeaways

1. Brute Force is Too Slow – O(n²) is infeasible for large inputs.
2. One-Pass is Optimal – Tracks min price and max profit efficiently.
3. Handles Edge Cases – Returns 0 if prices are non-increasing.

FAQs

Q1: What if the stock price keeps decreasing?

The algorithm returns 0 because no profitable transaction is possible.

Q2: Can this handle duplicate prices?

Yes. The solution focuses on profit, not unique prices.

Q3: Why not use a sliding window?

The one-pass method is already optimal. Sliding window would not improve efficiency.

Practice Variations

1. Best Time to Buy and Sell Stock II – Allows multiple transactions.
2. Best Time with Transaction Fee – Includes a fee for each transaction.

Mastered this problem? Share this guide to help others ace their coding interviews!

Keywords: Best time to buy and sell stock LeetCode, O(n) solution Java Python, maximum profit stock problem, one-pass algorithm, brute force vs optimal.

This post is fully optimized with structured headers, clean code snippets, and FAQ sections for clarity and engagement.