Two Sum: The Interview Question Everyone Asks (and How to Nail It)

If you have done more than a handful of technical interviews, you have met Two Sum. It is the opening act of LeetCode, a favorite warm-up at Google and Amazon, and the template for an entire family of "find the pair" problems. Because it is so common, interviewers rarely stop at the basic version — they use it to probe how you reason, optimize, and handle follow-ups. This post walks through the problem the way a strong candidate handles it live: naive solution first, then the optimization, then the questions that come after.

The problem

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. You may not use the same element twice, and there is exactly one solution.

Example:

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

Why do interviewers love this problem?

Two Sum is a test of one specific, transferable skill: recognizing that a lookup can replace a scan. That single observation separates candidates who memorize solutions from candidates who understand complexity tradeoffs. The problem is also deliberately simple — with no parsing traps or exotic data structures — so the interviewer can spend the whole session watching how you think: Do you state a baseline? Do you name the complexity unprompted? Do you notice the edge cases? Do you handle hints well?

The same "remember what you have seen" trick powers dozens of other problems — subarray-sum-equals-k, longest substring without repeating characters, count of good pairs — so interviewers use Two Sum as a cheap probe of a pattern that pays off everywhere.

Step 1: Start with the brute force (always)

Even if you see the optimal solution immediately, say the naive one first. Interviewers want to watch your problem-solving process, and stating the obvious baseline gives you a floor to improve on — plus something to compare against when you optimize.

The brute force is straightforward: check every pair.

def two_sum(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):   # j > i: never reuse an element
            if nums[i] + nums[j] == target:
                return [i, j]

State the complexity out loud: O(n²) time because we test all pairs, O(1) extra space. Then ask the magic question: "Can we trade space for time?" That single question leads to the optimal solution — and saying it out loud is what the interviewer is grading.

Step 2: The hash map insight

Here is the key observation. When we look at a number x, we are not really searching for "some pair" — we are searching for exactly one number: target - x. Instead of scanning the rest of the array for that partner, we can remember every number we have already seen in a hash map from value to index. Then each lookup is O(1) average time.

def two_sum(nums, target):
    seen = {}                        # value -> index of first occurrence
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:       # partner already passed by?
            return [seen[complement], i]
        seen[x] = i                  # record AFTER checking: never reuse i

Walk through the example: at index 0, x = 2, complement 7 — not seen yet, so store 2 -> 0. At index 1, x = 7, complement 2 — present at index 0. Return [0, 1].

Two details deserve deliberate attention, because interviewers probe them:

• Check before inserting. If you inserted seen[x] = i first, an element could pair with itself (e.g. target = 4, x = 2). Checking first guarantees we never reuse the same index — the fix is one line, and noticing it unprompted scores points.
• Store the index, not just the value. The problem asks for indices, and duplicates make this subtle: keeping the first occurrence's index is correct here because any valid partner for a duplicate must come later.

Time: O(n) — one pass, O(1) average work per element. Space: O(n) — the map of seen values.

Complexity quick reference

| Approach | Time | Space | When to use | | --- | --- | --- | --- | | Brute force pairs | O(n²) | O(1) | Name it first as the baseline; rarely the final answer | | Hash map | O(n) | O(n) | Unsorted input, single pass, indices required | | Two pointers | O(n) | O(1) | Sorted input (or sortable), memory-constrained |

Follow-up variants to expect

"What if the array is sorted?"

Now two pointers shine: one pointer at each end; move the left pointer up or the right pointer down depending on whether the current sum is too small or too large. That is O(n) time, O(1) space — better than the hash map. Being able to switch techniques when the input changes is exactly what this follow-up tests.

"What if there can be multiple valid pairs?"

Return all of them. With the hash map, collect matches as you scan (mind duplicates — only count each pair once). With sorted two pointers, when a match is found, skip duplicate values on both sides. Mentioning duplicates unprompted shows you think about edge cases before being asked.

"Return the values instead of the indices" (or: k-diff pairs)

Once you return values, sorting becomes viable and the two-pointer approach is clean. For k-diff pairs (count pairs with |a - b| == k), sort and use two pointers, or use a hash set of seen values with the x + k complement check — the same hash instinct as Two Sum itself.

"What about Three Sum?"

Fix one element, then solve Two Sum on the remainder — O(n²) overall, and the natural bridge into the whole class of sum problems. Mentioning this decomposition unprompted signals strong pattern recognition; interviewers at larger companies frequently follow this exact path.

How to talk through it in the interview

Here is a compact script for the live performance:

1. Restate and clarify. "Exactly one solution, can't reuse an index, return indices — got it. Any constraints on size or value ranges?" (You may not need the answer; asking is the point.)
2. Propose the baseline. "The straightforward approach is checking all pairs — O(n²), O(1) space. Let me see if I can do better."
3. Explain the insight before coding. "For each number I only need one specific partner: target minus it. If I remember what I've seen in a hash map, that lookup is constant time."
4. Code, narrate, name complexity. State O(n) time / O(n) space the moment you finish — don't wait to be asked.
5. Test out loud. Walk the example [2, 7, 11, 15], target 9 step by step, then an edge case: [3, 3], target 6 — the reason you check before inserting.
6. Invite the follow-up. "If the input were sorted, I'd switch to two pointers for O(1) space." You just pre-empted the interviewer's next question and looked in control.

The bottom line

Two Sum looks trivial, and that is the trap. Candidates who rush in, code the hash map, and go silent score worse than candidates who narrate the journey: baseline, insight, tradeoff, edge cases, follow-ups. Master the performance, not just the solution — and the most-asked question in interviewing becomes your warm-up lap.

Frequently Asked Questions

Is Two Sum asked in real interviews at big companies?

Yes, constantly — as a warm-up, a phone-screen opener, or the seed of a harder problem. Amazon, Google, and Meta all report it regularly, which is why it appears in prep plans like the Amazon OA guide.

Which solution should I give first in the interview?

Always name the brute force first, then optimize. Interviewers grade the reasoning journey, and the O(n²) baseline is what makes the O(n) improvement meaningful when you explain the tradeoff.

Why not just sort the array and use two pointers everywhere?

Because sorting costs O(n log n) time, destroys the original indices (the problem asks for them), and adds no benefit on unsorted input. If indices do not matter or the input is already sorted, two pointers are the better tool — that is the judgment call interviewers are probing.

What patterns should I learn right after Two Sum?

The complement-lookup family: subarray sum equals k (prefix sums + hash map), longest substring without repeating characters (sliding window), and then the sum family — Three Sum, Four Sum, and k-diff pairs. The 4-week prep plan sequences exactly this.

How do I know when a hash map is the right tool?

Whenever the question reduces to "have I seen this before?" or "does a partner of x exist?" — frequency counting, complement lookup, deduplication, first-occurrence problems. If you find yourself nesting a scan inside a loop to find something specific, a hash map probably removes the inner scan.