Two Sum — The Hash Map Pattern Every FAANG Engineer Knows

Problem Statement#

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

Constraints:

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Exactly one valid answer

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

Input:  nums = [3, 2, 4], target = 6
Output: [1, 2]

Why This Problem Matters#

Two Sum is the most-asked array interview question on the planet. Amazon and Google phone screens use it as a five-minute warmup to filter candidates who do not understand hash maps. If you brute force this in 2026, the loop ends quickly.

The pattern this question teaches — complement lookup — appears in 3Sum, 4Sum, Two Sum II, Subarray Sum Equals K, and many graph problems. Meta interviewers love it because the optimal answer is exactly one hash map and one pass, which leaves time for follow-ups about sorted variants and duplicates.

The Core Insight#

Brute force pairs every element with every other element in O(n^2). The bottleneck is finding the complement target minus num. A hash map turns that lookup from O(n) into O(1).

We never need both indices in the map. As we walk left to right, we ask have I already seen target minus nums[i]. If yes, we found the pair. If no, we store nums[i] and continue. One pass, one map.

The decision to store first or look up first matters because storing first would let an element pair with itself.

Visual Dry Run#

Solution (Optimal)#

class Solution:
    def twoSum(self, nums, target):
        seen = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i
        return []

var twoSum = function(nums, target) {
    const seen = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (seen.has(complement)) {
            return [seen.get(complement), i];
        }
        seen.set(nums[i], i);
    }
    return [];
};

Time: O(n) — one pass and O(1) average hash operations. Space: O(n) — the hash map stores up to n entries.

Common Mistakes#

• Looping twice with a nested loop after the interviewer asked for optimal.
• Storing nums[i] before checking the complement, which lets an element pair with itself when target equals two times nums[i].
• Returning the values instead of the indices.
• Assuming the input is sorted and using two pointers without confirming.
• Using a Set instead of a Map and losing the index.

Interview Tips#

• State brute force first, then identify lookup as the bottleneck.
• Walk through the 2, 7, 11, 15 with target 9 example before coding.
• Mention that hash collisions theoretically degrade to O(n), but average is O(1).
• After solving, ask if the array is sorted — that opens the two-pointer follow-up.

Follow-up Questions#

• What if the array is sorted? Hint: two pointers, O(1) space.
• What if there can be multiple pairs? Hint: store all indices in a list.
• What if you need all unique pairs of values? Hint: skip duplicates after sorting.
• What about Three Sum or Four Sum? Hint: fix one or two and reduce to Two Sum.
• What if the array does not fit in memory? Hint: external hash or sort plus two pointers.

Key Takeaways#

• LeetCode 1 Two Sum is solved in O(n) with a single hash map pass.
• Look up the complement before inserting the current element.
• Hash map space is O(n); two pointers on a sorted array is O(1).
• The complement pattern generalizes to 3Sum, 4Sum, and subarray sum problems.
• Brute force is O(n^2); never present it as your final answer.
• Map stores value to index, not index to value.
• This is the most common Amazon and Google phone screen warmup question.