1. Understanding the Problem

You are given an array called prices, where prices[i] represents the price of a given stock on the ith day.

Your goal is to maximize your profit by choosing exactly one day to buy one stock and choosing a different day in the future to sell that same stock. If no profit is possible, you must return 0.

The Core Constraints:

• You must buy before you sell. Time only moves forward.
• You can only complete exactly one transaction (one buy and one sell).

A Quick Example

Imagine prices = [7, 1, 5, 3, 6, 4].

If you buy on Day 2 (price = 1) and sell on Day 5 (price = 6), your profit is 6 - 1 = 5. You cannot buy on Day 2 and sell on Day 1, because you must buy first. The correct answer here is 5.

2. The Brute Force Approach (What to Avoid)

The most basic instinct is to check every possible pair of buy and sell days.

You would pick the first day as your buy day, then check all subsequent days to see what your profit would be. Then, you move your buy day to the second day, and check all future days again. You keep track of the highest profit you find.

Trade-off Analysis

While this logic is correct, it fails dramatically at scale:

• Time Complexity: O(N²) — For an array of 100,000 prices, you are making billions of comparisons. You will get a "Time Limit Exceeded" error.
• Space Complexity: O(1) — No extra memory is used, but the slow execution makes this approach unacceptable for production-grade systems.

3. The Optimal Approach: State Tracking (One Pass)

To optimize this, we need to bring our time complexity down to O(N). We can do this by traversing the array exactly once. The secret is to maintain two pieces of "state" (variables) as we move through time:

1. The lowest price we have seen so far.
2. The maximum profit we could get if we sold today.

Think about it logically: to maximize your profit on any given day, you would need to have bought the stock at the absolute lowest price available before that day. As we iterate through the days, if we find a new historically low price, we update our "lowest price" record. If we find a higher price, we calculate the profit against our recorded lowest price and update our "maximum profit" if it's the best we've seen.

4. The Logic Step-by-Step

1. Initialize a variable min_price to an infinitely large number (so the very first price will immediately become the new minimum).
2. Initialize a variable max_profit to 0.
3. Loop through every price in the prices array:
   • If the current price is less than min_price: Update min_price to be the current price. (We found a better day to buy).
   • Otherwise: Calculate the profit if we sold today (current price - min_price). If this profit is greater than our max_profit, update max_profit.
4. Return max_profit.

5. Complexity Analysis

• Time Complexity: O(N) — We only look at each price one time, making this solution incredibly fast and scalable.
• Space Complexity: O(1) — We only use two variables (min_price and max_profit), regardless of how large the input array is.

6. Code Implementations

Expand the sections below to see the optimal O(N) time and O(1) space implementations across different languages.

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0
    
    for price in prices:
        # If we find a new lower price, update our min_price
        if price < min_price:
            min_price = price
        # Otherwise, check if selling today yields a better profit
        elif price - min_price > max_profit:
            max_profit = price - min_price
            
    return max_profit

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }
        
        return maxProfit;
    }
}

#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) {
            if (price < minPrice) {
                minPrice = price;
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        
        return maxProfit;
    }
};

7. Conclusion: You Are Ready

By solving "Best Time to Buy and Sell Stock," you have trained your brain to think in a single pass. You now know how to intelligently store the history of an array (in this case, the lowest price seen so far) so that you don't have to repeatedly look backward. This concept is the gateway to Dynamic Programming and Sliding Window techniques. Study the logic, write the code from memory, and you will be completely prepared when this shows up in your next interview!