LeetCode Two Sum: Brute Force to O(n) Hash Map

Beginner 9 min read

What you'll learn

✓Brute-force approach and its complexity
✓Optimal approach with intuition
✓Edge cases that trip people up
✓How to talk through it in an interview
✓Related LeetCode problems to follow up with

Prerequisites

•Comfortable with arrays and hash maps

Two Sum is LeetCode problem 1 and it is rated Easy. It is also the single most common phone screen warm-up question in the industry, which makes it worth knowing cold. The interesting part is not the brute force solution; it is how cleanly the hash map version trades space for time.

The Problem

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target. You may assume each input has exactly one solution and you may not use the same element twice.

Example:

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] == 9

The output is a pair of indices, not values. That detail matters because it forces you to remember positions, not just numbers.

Brute Force

The obvious approach: for every element, scan the rest of the array looking for a complement.

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

Time complexity is O(n^2) because every pair is considered. Space is O(1). For n = 10^4 (the LeetCode constraint) this is roughly 10^8 operations, which will time out on some test cases. It is correct, but not acceptable.

Optimal Solution

The trick is to ask a different question. Instead of “does any pair sum to target?”, ask: “for the current number x, have I already seen target - x?” That question can be answered in O(1) with a hash map.

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return []

Walking through it line by line:

seen maps a number we have already visited to its index.
We iterate once with enumerate so we get both index i and value x.
complement = target - x is the number we need to pair with x.
If that complement is already in seen, we found our answer. Return the stored index and the current index, in that order so the smaller index comes first.
Otherwise we record x in seen and move on.

Notice we store x after checking. That ordering prevents pairing an element with itself when the array contains duplicates that should not be matched.

Walk Through an Example

Let nums = [3, 2, 4] and target = 6.

i = 0, x = 3. complement = 3. seen is empty. Store seen = {3: 0}.
i = 1, x = 2. complement = 4. Not in seen. Store seen = {3: 0, 2: 1}.
i = 2, x = 4. complement = 2. Found at index 1. Return [1, 2].

One pass, three hash lookups, done.

Edge Cases

Duplicates that form the answer, like nums = [3, 3] and target = 6. The “store after check” order handles this because by the time we see the second 3, the first 3 is already in the map.
Negative numbers. The math is identical, so no special handling is needed.
Targets that can never be reached. The problem guarantees a solution, but in a real interview clarify whether returning an empty list is acceptable.
Very large arrays. Python dicts have amortized O(1) lookup so this scales cleanly.

Complexity Analysis

Time: O(n). Every element is visited once. Hash lookups and inserts are O(1) amortized.
Space: O(n) for the hash map in the worst case where no pair is found until the very end.

This is the classic time-space tradeoff. If you have not already, read Big O notation explained for why O(n) beats O(n^2) decisively at scale.

How to Explain It in an Interview

Start by restating the problem and confirming inputs and outputs, especially that indices are returned, not values.
Walk through the brute force first so the interviewer knows you can see the baseline. Quote its complexity.
Pivot to the hash map idea by saying: “For each element I want to ask, in O(1), whether its complement is already on my left.”
Code it. Stress that you check the map before inserting to avoid self-pairing.
State the complexity out loud and acknowledge the space cost.
If asked for follow-ups, mention sorted variants and 3Sum.

If you need the underlying skill, our posts on arrays common operations and hashing and hash maps cover the building blocks.

Wrap up

Two Sum is the prototypical “see the hash map opportunity” problem. The moment you internalize “remember what I have seen so I can answer complement queries in O(1)”, you will start spotting the same shape everywhere from subarray sums to anagram grouping. Burn the pattern into muscle memory and the harder variants become straightforward.