Code

I started LeetCode

2 min read

Two Sum: From Brute Force to Hash Map

When solving Two Sum, I started with the simplest idea instead of trying to find the optimal solution immediately.

The problem asks us to find two different indices whose values add up to a target.

1. Start with the obvious approach

For every number, calculate the value we need:

req = target - nums[i]

Then search the array for that value.

My first working brute-force solution was:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        out = []

        for i in range(len(nums)):
            req = target - nums[i]

            for j in range(len(nums)):
                if nums[j] == req and i != j:
                    out.append(j)

        return out

The important debugging lesson here was remembering that we cannot use the same index twice.

2. Look for wasted work

The outer loop runs n times, and for every element the inner loop can also run n times.

So the brute-force approach is:

O(n²)

The main problem is that we repeatedly search the entire array for req.

That leads to the next question:

Can I remember numbers I’ve already seen so I don’t have to search for them again?

3. Use a hash map

A dictionary can store:

number -> index

While scanning the array, we check whether the required value has already appeared.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}

        for i in range(len(nums)):
            req = target - nums[i]

            if req in seen:
                return [seen[req], i]

            seen[nums[i]] = i

Dictionary lookup is typically O(1), so we only need one pass through the array.

Time:  O(n)
Space: O(n)

The main lesson

The useful pattern wasn’t just “use a hash map.”

The thought process was:

Build a simple solution
        ↓
Make it correct
        ↓
Find the repeated work
        ↓
Ask what information can be remembered
        ↓
Choose a data structure that makes lookup faster

A good signal for using a hash map is when you catch yourself repeatedly asking:

“Does this value exist, and where did I see it?”