LeetPrep

Two Sum: From Brute Force to Hash Map

Published October 12, 2026 · 3 min read

Two Sum is the first problem on LeetCode and a favourite warm-up question in interviews. It looks simple, but it teaches one of the most useful ideas in algorithms: you can often trade a little memory for a lot of speed.

The problem

You are given an array of integers nums and an integer target. Return the indices of the two numbers that add up to target. You may assume exactly one valid answer exists, and you may not use the same element twice.

Example: nums = [2, 7, 11, 15], target = 9. Since 2 + 7 = 9, the answer is [0, 1].

Approach 1: brute force

The first idea is to check every pair. For each index i, look at every later index j and test whether the two values add up to the target.

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]

This works, but it takes O(n²) time because of the two nested loops. For an array of 100,000 numbers that is billions of comparisons, which is too slow.

Approach 2: hash map in one pass

Instead of searching for a partner every time, ask a different question: for the current number n, what value would complete the pair? It is target - n. If we have already seen that value, we are done. A dictionary lets us check that in constant time.

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, n in enumerate(nums):
        need = target - n
        if need in seen:
            return [seen[need], i]
        seen[n] = i

We store each number only after checking for its partner. That small detail prevents us from using the same element twice and handles duplicates correctly. For nums = [3, 3] and target = 6, the first 3 is stored, and when we reach the second 3 we find its partner.

Complexity

Approach Time Space
Brute force O(n²) O(1)
Hash map O(n) O(n)

Edge cases to mention in an interview

  • Duplicate values, such as [3, 3].
  • Negative numbers and zero. The hash map approach handles them without changes.
  • If the array were sorted and you only needed the values, a two-pointer scan would use O(1) extra space.

The pattern to remember

Whenever you find yourself searching for a matching element inside a loop, ask whether a hash map can turn that search into a lookup. The same idea solves many problems, from counting subarrays with a given sum to finding anagram groups.

Keep learning