Two Sum — The HashMap Interview Question Asked at Every FAANG

Problem Statement#

Given an array nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution and the same element cannot be reused.

Constraints:

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

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

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

Why This Problem Matters#

LeetCode 1 Two Sum is the canonical hashmap interview question and the most-cited warm-up at Google, Amazon, Meta, Microsoft, and Apple phone screens. Recruiters use it because it instantly reveals whether a candidate reaches for a HashMap to convert search into O(1) lookup, or grinds through the obvious O(n^2) nested loop.

The hash table FAANG curriculum starts here. The complement-lookup pattern — store seen values, query for target - x — extends to 4Sum II, Two Sum IV (BST), and any problem where pairs sum to a target. Beyond interviews, the same idea drives database join indexes, in-memory rate-limiters, and feature-store lookups.

The one-pass HashMap also showcases a subtle correctness lesson: check before insert. Querying first guarantees the map only contains earlier indices, preventing self-pairing on inputs like [3, 3] with target = 6.

The Core Insight#

Brute force tries every pair (i, j) for an O(n^2) time bound. The reframe: for each nums[i], the missing partner is target - nums[i]. A HashMap keyed by value gives O(1) lookup of that partner. Walk the array once, asking "have I seen the complement?" before inserting the current value. The first hit is the answer.

The check-before-insert order is critical. If you insert first, querying target - nums[i] could return the index of nums[i] itself, falsely satisfying the constraint that the two indices must differ.

Visual Dry Run#

Input [3, 2, 4], target 6:

Solution (Optimal)#

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen: dict[int, int] = {}
        for i, x in enumerate(nums):
            need = target - x
            if need in seen:
                return [seen[need], i]
            seen[x] = i
        return []

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

Time: O(n) because each index is visited once and each map op is amortized O(1). Space: O(n) because the map can grow up to n entries when the answer pair is at the tail.

Common Mistakes#

• Inserting before querying. Causes self-pairing on inputs like [3, 3] with target 6.
• Using a HashSet instead of a HashMap. Sets confirm presence but lose the index needed for the answer.
• Pre-populating the map with all values. Breaks the same-element-twice rule when complement equals value.
• Forgetting that negative or zero target values are valid. The algorithm handles them with no special case.
• Confusing this with Two Sum II (sorted input). Sorted variant uses two pointers for O(1) extra space.

Interview Tips#

• State the brute force O(n^2), then narrate the lookup speedup before writing code.
• Use a Map in JavaScript, not a plain object, so numeric keys do not collide with prototype keys.
• Mention "amortized" when discussing O(1) hash ops; it shows hash-table fluency.
• If asked for follow-ups, contrast HashMap O(n) time and O(n) space with sort plus two pointers O(n log n) time and O(1) space.

Follow-up Questions#

• What if the array is sorted? (Hint: two pointers, O(1) extra space — LC 167.)
• What if there are multiple valid pairs? (Hint: collect into a result list and skip duplicates.)
• How would you support a streaming add and find API? (Hint: maintain a frequency map — LC 170.)
• Extend to 3Sum: fix one element and run Two Sum on the rest with two pointers.
• What if hash collisions are adversarial? (Hint: randomized seeds in CPython and V8.)

Key Takeaways#

• Two Sum is LeetCode 1 and the most asked FAANG hashmap interview question.
• The complement HashMap turns O(n^2) into O(n) by replacing a search with an O(1) lookup.
• Always check before insert to prevent the same index from pairing with itself.
• Hash maps store value to index, not just presence, because Two Sum needs the indices.
• HashMap O(n) time and O(n) space versus sort plus two pointers O(n log n) time and O(1) space.
• The same complement pattern generalizes to 4Sum II and Two Sum IV (BST).
• Use Map in JavaScript and dict in Python; both are amortized O(1) per op.