Two Sum — The Problem That Unlocks Every HashMap Interview Question

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. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:

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

Example 2:

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

Example 3:

Input:  nums = [3, 3], target = 6
Output: [0, 1]
Explanation: Two separate elements at different indices — not the same element used twice

• Why This Problem Matters
• The "Aha" Moment
• Visual Dry Run
• Common Mistakes
• Pattern Recognition
• Solutions
• Approach 1 — Brute Force O(n²)
• Approach 2 — One-Pass HashMap O(n) — Optimal
• Complexity Analysis
• Brute Force
• One-Pass HashMap (Optimal)
• Follow-up Questions
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

Two Sum holds the record as the single most-asked technical interview question across the industry — confirmed in 170+ interviews at 70 companies including Google, Meta, Amazon, Microsoft, and Bloomberg. But here is the uncomfortable truth: most candidates who solve it still fail the interview. Why? Because the solution is not the point. Interviewers use Two Sum as a diagnostic. In the first 10 minutes they want to know: Can you recognize when a problem has a brute-force trap? Do you instinctively reach for the right data structure? Can you explain the trade-off between time and space clearly and confidently? Can you handle follow-up constraints without freezing? The problem is a controlled environment that reveals your entire problem-solving playbook in under 15 minutes. Treat it that way.

The "Aha" Moment

Let's forget code for a moment and just think.

You have a list of numbers. You need two of them to add up to a target. The obvious approach — the one every brain defaults to first — is to check every pair. Pick one number, check it against every other number. That works. It is also slow: for 10,000 numbers, you make up to 50 million comparisons. Interviewers call this the O(n²) trap.

Here is the insight that changes everything.

When you're standing at any number x in the array, you do not need to search for its partner. You already know exactly what the partner must be: target - x. If target is 9 and you are looking at 2, the partner must be 7. There is no ambiguity.

The only question is: have I already seen 7?

And this is where the hashmap comes in. A hashmap lets you answer "have I seen this value before, and if so, at which index?" in constant time — O(1). No loop. No search. Just one dictionary lookup.

So the entire algorithm becomes: as you walk through the array, for each number, check if its required partner is already stored in your hashmap. If it is, you have your answer. If it is not, store the current number and move on.

You are not searching forward. You are remembering backward.

This mental shift — from "find the partner" to "remember what I've seen and check for the partner" — is the foundation for dozens of interview problems. Once you see it here, you will recognize it everywhere.

Visual Dry Run

Let's trace nums = [2, 7, 11, 15], target = 9 step by step.

HashMap (seen) starts empty: {}

Step 1 — i=0, num=2
  complement = 9 - 2 = 7
  Is 7 in seen? No → store {2: 0}

  seen = {2: 0}

Step 2 — i=1, num=7
  complement = 9 - 7 = 2
  Is 2 in seen? YES → index stored is 0
  Return [seen[2], current_i] = [0, 1] ✓

  Done.

Now let's trace nums = [3, 2, 4], target = 6 to see a case where the answer is not at index 0:

HashMap (seen) starts empty: {}

Step 1 — i=0, num=3
  complement = 6 - 3 = 3
  Is 3 in seen? No → store {3: 0}

  seen = {3: 0}

Step 2 — i=1, num=2
  complement = 6 - 2 = 4
  Is 4 in seen? No → store {2: 1}

  seen = {3: 0, 2: 1}

Step 3 — i=2, num=4
  complement = 6 - 4 = 2
  Is 2 in seen? YES → index stored is 1
  Return [seen[2], current_i] = [1, 2] ✓

Notice something critical: we check for the complement before storing the current number. This prevents accidentally using the same element twice. If nums = [3, 3] and target = 6, when we are at index 0 (num=3), its complement is also 3 — but we check first and 3 is not in the map yet. We store {3: 0}. Then at index 1 (num=3), complement is 3, and now it is in the map at index 0. We return [0, 1]. Two different indices, two different elements. Correct.

Common Mistakes

These are the mistakes that real candidates make in real interviews — not edge cases you need a test suite to catch, but thinking errors that happen live under pressure.

1. Using the same element twice. The problem explicitly says "you may not use the same element twice." When nums = [3, 3], target = 6, the correct answer is [0, 1] — two different indices that both hold the value 3. The mistake is thinking duplicates are invalid. They are not. The constraint is on index reuse, not value reuse. The one-pass approach handles this automatically by checking before inserting.

2. Returning values instead of indices. The problem asks for indices. Not the numbers themselves. This sounds obvious until you are nervous and you write return [num, complement] instead of return [seen[complement], i]. The hashmap must store value → index, not just the values.

3. Doing two passes when one is enough — and not knowing why it matters. Some candidates implement a two-pass approach: first build the entire hashmap, then scan the array again to find complements. This works correctly, but interviewers will ask you: "Can you do it in one pass?" If you cannot answer confidently, you have exposed a gap. The one-pass approach is not just faster in practice (same O(n) complexity, but one fewer traversal) — it demonstrates you understand why you are adding elements to the map during traversal rather than before it.

4. Not clarifying constraints before coding. Interviewers at top companies want you to ask questions before writing a single line of code. Questions like: "Can there be negative numbers?" (yes, and the algorithm handles it fine), "Is there always exactly one solution?" (per the problem, yes — but ask anyway), "Can the array be empty?" (worth discussing). Jumping straight into code signals you do not think about problem constraints, which is a red flag.

Pattern Recognition

Two Sum belongs to the hashmap complement lookup pattern. The signature of this pattern is:

• You are searching for two (or more) elements that satisfy a relationship (sum, difference, product, etc.)
• A brute-force nested loop exists but is too slow
• For each element, the "partner" value is deterministic — you can compute it exactly

When you see this in an interview, the instinct should be: compute the complement, check the hashmap, store and move on.

This exact pattern, with minor modifications, powers:

• 3Sum — fix one element, reduce to Two Sum on the rest with two pointers
• Subarray Sum Equals K — use prefix sums as keys, same complement lookup
• Two Sum II (sorted input) — use two pointers instead of hashmap since sorting is given
• Four Sum — nested Two Sum, same core logic
• Longest Consecutive Sequence — hashset membership check, same "have I seen this?" logic

Recognizing the pattern is worth more than memorizing any individual solution.

Solutions

Approach 1 — Brute Force O(n²)

Check every possible pair. Simple to understand, too slow for large inputs.

Python

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)

        # Outer loop: pick the first element of the pair
        for i in range(n):
            # Inner loop: check every element after i (avoid reusing same index)
            for j in range(i + 1, n):
                # If the two elements sum to target, we found the answer
                if nums[i] + nums[j] == target:
                    return [i, j]

        # Problem guarantees a solution exists, so this line is never reached
        return []

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
    const n = nums.length;

    // Outer loop: pick the first element of the pair
    for (let i = 0; i < n; i++) {
        // Inner loop: check every element after i (never reuse the same index)
        for (let j = i + 1; j < n; j++) {
            // If these two elements sum to target, return their indices
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }

    // Problem guarantees exactly one solution — this is unreachable
    return [];
}

Approach 2 — One-Pass HashMap O(n) — Optimal

Walk the array exactly once. For each element, check if its complement is already in the map. If yes, return immediately. If no, store the current element and continue.

Python

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Maps each number we've seen to its index in the array
        seen = {}

        for i, num in enumerate(nums):
            # The exact value we need to find in order to reach the target
            complement = target - num

            # If we've already seen the complement, we have a valid pair
            if complement in seen:
                # seen[complement] is the earlier index; i is the current index
                return [seen[complement], i]

            # Store current number AFTER checking — prevents using the same
            # element twice (e.g., num=3, target=6: complement=3, but we
            # check before storing, so we don't match index i with itself)
            seen[num] = i

        # Unreachable given the problem's guarantee of exactly one solution
        return []

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
    // Maps each number we've seen to its index in the array
    const seen = new Map();

    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];

        // The exact value we need to have seen previously
        const complement = target - num;

        // If the complement is already in the map, we have our pair
        if (seen.has(complement)) {
            // seen.get(complement) is the earlier index; i is the current one
            return [seen.get(complement), i];
        }

        // Store AFTER checking to avoid matching an element with itself
        seen.set(num, i);
    }

    // Unreachable — problem guarantees exactly one solution
    return [];
}

Complexity Analysis

Brute Force

One-Pass HashMap (Optimal)

The trade-off is explicit and important to articulate in interviews: you give up O(n) extra space to eliminate an entire loop. For arrays of size n=10,000, the difference between O(n²) and O(n) is the difference between 100 million operations and 10,000. That is not a minor optimization — it is the difference between a timeout and an accepted solution.

A note on the two-pass hashmap: Some solutions build the entire hashmap first (pass 1), then scan for complements (pass 2). This is still O(n) time and O(n) space — the big-O is identical. But it requires two full traversals instead of one, and it needs extra care to avoid matching an element's complement with itself. The one-pass approach handles both issues elegantly. If your interviewer asks "can you do this in one pass?" and you implemented two-pass, that is the distinction they are testing.

Follow-up Questions

These are the actual follow-up questions that appear in Google, Meta, and Amazon interviews after you solve the base problem. Each one tests a different dimension of your understanding.

Q1: What if the array is sorted — can you do better on space?

Yes. When the array is sorted, use two pointers: one at the start, one at the end. If their sum is too large, move the right pointer left. If too small, move the left pointer right. This is O(n) time and O(1) space — no hashmap needed. This is exactly LeetCode 167 (Two Sum II). The key insight: sorting gives you directional information that makes the two-pointer sweep possible.

Q2: What if there are multiple valid pairs — return all of them?

Change the return from a single result to a list. Instead of returning immediately when you find a match, append [seen[complement], i] to a results list and continue. Be careful with duplicates — if nums = [1, 3, 3, 1] and target = 4, you should return both [0, 3] and [1, 2]. Ask the interviewer whether the results should be deduplicated.

Q3: What if the numbers come from a data stream (you cannot store the whole array)?

You cannot use the two-pointer trick because you cannot sort a stream. Use a hashset instead of a hashmap. For each new number x arriving from the stream, check if target - x is in the set. If yes, you found a pair (though you cannot return indices since streaming problems usually ask for a boolean). If no, add x to the set. This is O(1) per element, O(k) space where k is the number of distinct elements seen.

Q4: What if the array can be very large and memory is constrained?

Discuss the space-time trade-off honestly. If memory is severely constrained, the brute force O(1) space approach may be the right engineering decision despite its O(n²) time cost. Alternatively, if the array can be sorted (and you do not need to preserve original indices), sort it first in O(n log n) and use two pointers for O(1) extra space. In interviews, acknowledging this trade-off explicitly — rather than assuming optimal time is always the goal — signals senior-level thinking.

Q5: How would you extend this to Three Sum (find three numbers that add to a target)?

Fix one element at a time with an outer loop. For each fixed element nums[i], reduce the problem to Two Sum on the remaining subarray with target - nums[i] as the new target. Sort the array first to enable the two-pointer approach on the inner Two Sum, and skip duplicate values to avoid duplicate triplets. Overall complexity: O(n²) time, O(1) extra space (not counting output). This is LeetCode 15 and one of the most common Two Sum follow-ups across all FAANG companies.

This Pattern Solves

The complement-lookup hashmap pattern you learned here directly applies to these problems — no new concepts required:

• LeetCode 167 — Two Sum II (Input Array Is Sorted): same problem, replace hashmap with two pointers
• LeetCode 15 — 3Sum: fix one element, run Two Sum on the rest
• LeetCode 560 — Subarray Sum Equals K: prefix sums as keys, complement lookup for target - prefix
• LeetCode 128 — Longest Consecutive Sequence: hashset membership, same "have I seen this?" lookup

Key Takeaway

The core insight of Two Sum is not the hashmap — it is the realization that trading O(n) space for O(n) time is often the right call, and that when you need a partner value, a hashmap lets you check "have I seen it?" in constant time instead of searching. Master this pattern and you have the foundation for a third of all array and string interview problems you will encounter.