Best Time to Buy and Sell Stock — From Brute Force to One-Pass Insight

Overview

You’re given a list of stock prices where each index represents a day. You are allowed only one transaction:

• Buy on one day
• Sell on a future day

Your goal is simple: maximize profit. If no profit is possible, return 0.

Problem Constraints

• 1 <= prices.length <= 10^5
• Expected time complexity: O(n)
• Only one buy and one sell
• Sell must happen after buy

How I Approached the Problem

I follow a strict rule when solving problems like this:

1. Make it work
2. Then make it fast

So I deliberately explored multiple approaches—even incorrect ones—to understand what doesn’t work and why.

Brute Force Approach

The most straightforward idea:

• Try every possible buy day
• Try every possible sell day after it
• Track the maximum profit

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        int n = prices.size();

        for (int buy = 0; buy < n; buy++) {
            for (int sell = buy + 1; sell < n; sell++) {
                profit = max(profit, prices[sell] - prices[buy]);
            }
        }

        return profit;
    }
};

Complexity

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

Why This Fails

With n up to 10^5, this approach performs billions of comparisons.

It works logically—but fails practically due to TLE.

Failed Attempts (and Why They Matter)

Before landing on the optimal solution, I tried a couple of “clever” ideas. They didn’t work—but they taught me why the correct solution does.

Attempt 1: Two Pointer Approach

Idea:

• Buy pointer at the start
• Sell pointer at the end
• Move pointers based on price comparison

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int i = 0, j = n - 1;
        int profit = INT_MIN;

        while (i < j) {
            profit = max(profit, prices[j] - prices[i]);

            if (prices[i] > prices[j]) i++;
            else j--;
        }

        return max(profit, 0);
    }
};

Why It Fails

• Prices are not sorted
• Valid buy–sell pairs are skipped
• Pointer movement is based on assumptions that don’t hold

This approach looks elegant but breaks under real input.

Attempt 2: Sell at Maximum Price

Idea:

• Find the highest price in the array
• Buy at the lowest price before it

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) return 0;

        int maxSell = INT_MIN;
        int maxSellIndex = 0;

        for (int i = n - 1; i >= 0; i--) {
            if (prices[i] > maxSell) {
                maxSell = prices[i];
                maxSellIndex = i;
            }
        }

        int profit = 0;
        for (int i = 0; i < maxSellIndex; i++) {
            profit = max(profit, maxSell - prices[i]);
        }

        return profit;
    }
};

Why It Fails

• Selling at the highest price doesn’t always give max profit
• The optimal buy–sell pair may happen earlier or later

Optimal Solution — One Pass

The Key Insight

You don’t need to know the future.

You only need two things:

• The minimum price so far
• The best profit so far

At each day:

• Assume you sell today
• Check if today’s price minus the lowest past price improves profit

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = prices[0];
        int profit = 0;

        for (int i = 0; i < prices.size(); i++) {
            buy = min(buy, prices[i]);
            profit = max(profit, prices[i] - buy);
        }

        return profit;
    }
};

Complexity

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

Why This Works

• Buying always happens before selling
• The lowest price is tracked dynamically
• Each element is processed exactly once
• No unnecessary comparisons or assumptions

This is optimal in both theory and practice.

Final Takeaways

• Don’t jump straight to optimization
• Failed approaches clarify constraints better than successful ones

If you can explain why your failed solution failed, you understand the problem.

That’s the real win.