Time Complexity: $O(N^2)$ The nested loops result in a quadratic number of comparisons. For an input size of $N = 10^5$, this results in approximately $10^{10}$ operations.

Why it fails: This approach fails due to Time Limit Exceeded (TLE) on large inputs. The constraints specify up to $100,000$ days, requiring an algorithm with linear $O(N)$ or log-linear $O(N \log N)$ complexity.

Core Insight for Best Time to Buy and Sell Stock

The transition from the brute force $O(N^2)$ approach to the optimal $O(N)$ approach relies on a single observation: to maximize profit when selling on day i, we must have bought the stock at the absolute lowest price occurring before day i.

We do not need to compare day i with every single previous day. Instead, we only need to know the minimum price seen so far. This allows us to maintain a running state as we traverse the array.

Invariant: At any index i, we maintain two values:

1. min_price: The lowest price encountered in prices[0...i].
2. max_profit: The maximum profit achievable using any sell date up to i.

Visual Description: Visualize the array of prices as a line graph where the x-axis represents days and the y-axis represents price. As we scan the graph from left to right, we maintain a "floor" line at the lowest y-value encountered. For every new point on the graph, we calculate the vertical distance between the current point and this floor. If the current point is below the floor, the floor updates to this new low. If the current point is above the floor, the vertical distance represents a potential profit. We record the largest vertical distance observed during the entire scan.

Execution Flow

Consider the input prices = [7, 1, 5, 3, 6, 4].

1. Initialization:

   • min_price = $\infty$
   • max_profit = 0

2. Iteration:

   • Day 0 (Price 7):
     • $7 < \infty$, so min_price becomes 7.
     • Profit calculation skipped (can't sell on buy day/price dropped).
   • Day 1 (Price 1):
     • $1 < 7$, so min_price becomes 1.
     • Price dropped, so we update our "buy" potential.
   • Day 2 (Price 5):
     • $5 > 1$. Potential profit = $5 - 1 = 4$.
     • max_profit becomes $\max(0, 4) = 4$.
   • Day 3 (Price 3):
     • $3 > 1$. Potential profit = $3 - 1 = 2$.
     • max_profit remains 4 ($4 > 2$).
   • Day 4 (Price 6):
     • $6 > 1$. Potential profit = $6 - 1 = 5$.
     • max_profit becomes $\max(4, 5) = 5$.
   • Day 5 (Price 4):
     • $4 > 1$. Potential profit = $4 - 1 = 3$.
     • max_profit remains 5.

3. Result: Return 5.

Proof of Correctness

The algorithm is correct because it exhaustively checks the optimal sell scenario for every single day. For any given day k acting as the sell day, the optimal buy day must be the day with the minimum price in the range 0 to k-1. By maintaining min_price as the running minimum, we guarantee that for every prices[i], we compute prices[i] - min(prices[0]...prices[i]). Since the global maximum profit must occur on some sell day, taking the maximum of all these local optimal choices yields the correct global maximum.

Reference Implementation

C++ Solution for LeetCode 121

cpp
#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        int minPrice = INT_MAX;
        int maxProfit = 0;

        for (int price : prices) {
            // Update the minimum price encountered so far
            if (price < minPrice) {
                minPrice = price;
            } 
            // Calculate potential profit if we sell at current price
            else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        
        return maxProfit;
    }
};

Java Solution for LeetCode 121

java
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            // Update the minimum price encountered so far
            if (price < minPrice) {
                minPrice = price;
            } 
            // Calculate potential profit if we sell at current price
            else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        
        return maxProfit;
    }
}

Python Solution for LeetCode 121

python
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        
        for price in prices:
            # Update the minimum price encountered so far
            if price < min_price:
                min_price = price
            # Calculate potential profit if we sell at current price
            else:
                current_profit = price - min_price
                if current_profit > max_profit:
                    max_profit = current_profit
                    
        return max_profit

Q: Why is my output wrong when prices are descending (e.g., [7, 6, 4, 3, 1])?

• Mistake: Initializing max_profit to Integer.MIN_VALUE or a negative number, or failing to handle the case where no profit is possible.
• Why: The problem states that if no profit can be achieved, return 0.
• Consequence: Returning a negative value is incorrect based on the problem specification.

Q: Why can't I simply find the index of the minimum value and the index of the maximum value?

• Mistake: Finding min(prices) and max(prices) independently and subtracting them.
• Why: The minimum price might appear after the maximum price in the array (e.g., [5, 1]). You cannot sell before you buy.
• Consequence: This logic violates the temporal constraint of the problem.