From Brute Force to Optimal: How I Learned to Think Like a Stock Market Jedi

The Quest Begins (The “Why”)

Ever felt like you’re stuck in a loop, watching the same scene over and over until you start quoting the movie? That was me last Tuesday, staring at a LeetCode problem titled “Best Time to Buy and Sell Stock”. The prompt was simple: given an array where each element is the price of a stock on day i, return the maximum profit you could make from one buy‑sell transaction.

My first instinct? “Let’s just check every possible pair.” I whipped out a nested loop, felt like Neo dodging bullets in The Matrix — except I was the one getting hit by O(n²) time every single test case. The brute force solution crawled through the array like a slug in a marathon, and for an input of 10⁵ elements it timed out harder than the final boss in Dark Souls after you forget to upgrade your weapon.

I was frustrated, but also curious. Why did it feel so… unnecessary? There had to be a smarter way to stare at those numbers and instantly know the best deal.

The Revelation (The Insight)

The breakthrough came when I stopped thinking about “pairs” and started thinking about “state”.

Imagine you’re walking through a market, watching the price ticker scroll by. At any moment, you only need to know two things:

1. The lowest price you’ve seen so far (the best buying opportunity up to today).
2. The biggest profit you could have made if you sold today (today’s price minus that lowest price).

If you keep those two numbers updated while you scan the array once, you’ve already considered every possible buy‑sell pair — without ever nesting a loop. It’s like realizing you don’t need to memorize every move in a chess game; you just need to keep track of the strongest threat and your best counter‑move.

That’s the mental framework top coders use: look for a running aggregate that captures the essence of all previous choices. In this case, the running minimum is the aggregate. The moment I saw it, I felt like Indy discovering the hidden map in Raiders of the Lost Ark — suddenly the whole maze made sense.

Wielding the Power (Code & Examples)

The “Brute Force” Trap

def max_profit_brute(prices):
    n = len(prices)
    best = 0
    for i in range(n):               # choose a buy day
        for j in range(i + 1, n):    # choose a sell day after i
            profit = prices[j] - prices[i]
            if profit > best:
                best = profit
    return best

What’s wrong here?

• It’s O(n²) — fine for tiny inputs, but it blows up on anything realistic.
• Easy to slip into an off‑by‑one mistake (using range(i, n) would let you sell on the same day, which isn’t allowed).
• You keep recomputing the same subtractions over and over; the work feels pointless after the first few iterations.

I ran this on a test case with 200 k prices and watched my CPU fan scream like a Wookiee in pain.

The “Optimal” Spell

def max_profit_optimal(prices):
    # Edge case: less than two days → no transaction possible
    if len(prices) < 2:
        return 0

    min_price_so_far = prices[0]   # the best buy price we've seen
    max_profit = 0                 # best profit we can achieve

    for price in prices[1:]:
        # If we sold today, profit would be price - min_price_so_far
        profit_today = price - min_price_so_far
        if profit_today > max_profit:
            max_profit = profit_today

        # Update the lowest price seen so far
        if price < min_price_so_far:
            min_price_so_far = price

    return max_profit

Why this feels like a cheat code:

• One pass → O(n) time, O(1) space.
• No nested loops, no redundant work.
• The two variables (min_price_so_far and max_profit) are the state we carry forward — exactly what the insight told us to track.

Common traps to avoid:

1. Forgetting the edge case – if the array length is 0 or 1, you can’t make a transaction; returning 0 is correct, but many beginners mistakenly start with min_price = float('inf') and end up with a nonsense profit.
2. Updating min_price_so_far after computing profit – you must compute profit using the minimum from previous days only. If you update the min first, you could accidentally allow buying and selling on the same day (profit = 0) and miss a better earlier buy.
3. Using max/min built‑ins inside the loop – they hide the O(1) intent and can tempt you to recompute over a slice, turning the solution back into O(n²). Keep it explicit, as shown.

Run the same 200 k‑price test case and watch the runtime drop from seconds to a few milliseconds — like switching from a horse‑drawn carriage to a Millennium Falcon jump to hyperspace.

Why This New Power Matters

This pattern — track a running extreme while scanning — shows up everywhere:

• Maximum subarray sum (Kadane’s algorithm) – keep the best sum ending at the current index.
• Longest substring without repeating characters – maintain a sliding window’s left bound.
• Minimum number of jumps to reach the end of an array – keep the farthest reachable index so far.

Once you internalize the idea of “what do I need to know from the past to make the best decision right now?”, you stop grinding on brute force and start spotting these one‑pass opportunities everywhere. It’s the difference between swinging a lightsaber wildly and letting the Force guide your blade.

Now, when I see a problem that asks for “the best … given a sequence”, my first question is: “What running value would let me compute the answer in O(1) per step?” That little shift turned a frustrating afternoon into a feeling of triumph — like finally destroying the Death Star after hours of dodging turbolaser fire.

Your Turn

Grab a problem you’ve solved with brute force before (maybe “Contains Duplicate”, “Two Sum”, or “Best Time to Buy and Sell Stock II”). Try to reframe it: what single piece of information from the prefix do you need to keep? Write the one‑pass version, test it, and notice how the runtime improves.

Drop your solution or aha moment in the comments — let’s celebrate each other’s quests from brute force to optimal! May the Force (and a good running minimum) be with you. 🚀