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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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.