From brute force to optimal: how to level up your solutions — Level Up Like Mario

The Quest Begins (The "Why")

I still remember the first time I tried to solve the “Two Sum” problem on a coding interview site. The statement was simple: given an array of integers and a target value, return the indices of the two numbers that add up to the target. My instinct was to grab two loops, check every pair, and return the first match. It worked on the tiny examples, but as soon as the test suite threw a 10 000‑element array at me, my solution slowed to a crawl. I felt like I was trying to defeat a final boss with a wooden sword — lots of effort, zero progress.

That frustration sparked a question: Is there a smarter way to look for the complement of each number instead of scanning the whole array every time? I started scribbling on a napkin, thinking about how I could remember what I’ve already seen. That napkin became the breakthrough that turned a sluggish O(n²) grind into a sleek O(n) victory.

The Revelation (The Insight)

The insight is deceptively simple: while iterating through the array, keep a hash map (or dictionary) that stores each number you’ve seen as a key and its index as the value. For the current element x, the value you need to reach the target is target - x. If that complement already exists in the map, you’ve instantly found the pair — no inner loop required.

It’s like walking into a room and instantly spotting the exact tool you need on a shelf, instead of rummaging through every drawer. The moment it clicked for me was when I realized the hash map does the heavy lifting of “remembering” for free — O(1) average lookup — turning the whole problem into a single pass.

I still grin when I think about it: it felt like when Neo dodges bullets in The Matrix, seeing the underlying pattern and moving through it with ease. That’s the power of trading brute force for a bit of clever bookkeeping.

Wielding the Power (Code & Examples)

The brute‑force attempt (the trap)

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

What’s wrong?

• The nested loops give O(n²) time.
• It’s easy to accidentally reuse the same index (i == j) if you’re not careful — hence the j = i + 1 start.
• For large inputs, this will time out, and you’ll waste precious interview minutes staring at a spinner.

The optimal solution (the spell)

def two_sum_optimal(nums, target):
    """
    Returns indices of the two numbers that add up to target.
    Assumes exactly one solution exists (as per the classic problem).
    """
    seen = {}                     # number -> its index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:    # <-- the aha! moment
            return [seen[complement], i]
        seen[num] = i             # remember this number for future complements
    return None                  # no solution found

Why this works:

• Each element is processed once → O(n).
• The dictionary lookup (complement in seen) is amortized O(1).
• We store only what we’ve seen, so space is O(n) in the worst case — a fair trade for the speed gain.

Common pitfalls to avoid:

1. Checking after insertion – If you add the current number to seen before checking for its complement, you might mistakenly pair the number with itself when target == 2 * num. Always check first, then insert.
2. Using a list instead of a dict – Trying to if complement in nums[:i] brings us back to O(n²) because list slicing and searching are linear. Stick with a hash map for constant‑time look‑ups.

A quick test run

print(two_sum_optimal([2, 7, 11, 15], 9))   # → [0, 1]
print(two_sum_optimal([3, 2, 4], 6))        # → [1, 2]
print(two_sum_optimal([3, 3], 6))           # → [0, 1]

All pass instantly, even with a million‑sized list.

Why This New Power Matters

Mastering this pattern does more than solve Two Sum. It’s the foundation for countless challenges:

• Subarray sum equals K – store prefix sums and look for current_sum - K.
• Number of good pairs – count frequencies as you go.
• Four Sum, 3Sum Closest, etc. – the same “remember what you’ve seen” idea appears in many guises.

When you internalize the habit of asking, “What information do I need to have already seen to make the current step O(1)?” you start seeing opportunities everywhere. Your solutions shift from “try every possibility” to “let the data guide you.” That mindset shift is what separates a coder who can grind through easy problems from one who can tackle hard ones with confidence.

---

Your Turn

Pick a problem you’ve solved with brute force before — maybe “contains duplicate” or “find the majority element.” Try to reframe it using a hash‑map‑based single pass. Did you spot the complement pattern? Did it feel like unlocking a secret level?

Drop your before/after code in the comments, share the “aha!” moment that made it click, and let’s keep leveling up together — no wooden swords required. Happy coding!