Two Sum — From Brute Force to O(n) Hash Map

Two Sum is rated Easy and is 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.

Intuition

The obvious approach is to consider every pair: for every element, scan the rest of the array looking for a complement. That nested loop is O(n^2) time and O(1) space, and for n around 10^4 it will time out on some test cases.

The trick to do better 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. We trade O(n) space for an order-of-magnitude speedup in time.

The key implementation detail: store each element in the map after checking. That ordering prevents pairing an element with itself when the array contains duplicates that should not be matched.

Explanation with 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.

nums   = [ 3 , 2 , 4 ]   target = 6
          i=0  i=1  i=2

i=0  x=3   complement=3   seen={}            -> store
                        seen={3:0}

i=1  x=2   complement=4   seen={3:0}         -> store
                        seen={3:0, 2:1}

i=2  x=4   complement=2   seen={3:0, 2:1}    -> hit!
                        return [seen[2], 2] = [1, 2]

step 1: look up (target - x) in seen   <-- check first
step 2: if found, return [seen[c], i]
step 3: otherwise seen[x] = i           <-- insert after

       +-----------+      +-----------+
x ---> |  lookup   | ---> |  insert   |
       | O(1) avg  |      | O(1) avg  |
       +-----------+      +-----------+

Code

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 []

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int c = target - nums[i];
            if (seen.containsKey(c)) return new int[]{seen.get(c), i};
            seen.put(nums[i], i);
        }
        return new int[0];
    }
}

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> seen;
        for (int i = 0; i < (int)nums.size(); i++) {
            int c = target - nums[i];
            if (seen.count(c)) return {seen[c], i};
            seen[nums[i]] = i;
        }
        return {};
    }
};

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. Hash maps 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.

Related Problems

• Two Sum II Input Array Is Sorted
• 3Sum
• 4Sum
• 4Sum II
• Two Sum III Data Structure Design

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” question. 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.