Two Sum

1. Problem & Core Objective

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 assume exactly one valid answer exists, and you may not use the same element twice.

Input:  nums = [2, 7, 11, 15], target = 9     Output: [0, 1]     (2 + 7 = 9)
Input:  nums = [3, 2, 4],      target = 6     Output: [1, 2]     (2 + 4 = 6)
Input:  nums = [3, 3],         target = 6     Output: [0, 1]

Constraints:

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

What the interviewer is actually testing

This is the most-asked coding question in existence, which means everyone has memorized it. The interviewer knows that. So what's actually being assessed is:

1. Can you derive the hash map solution, or only recite it? The difference shows immediately in how you explain it.
2. Do you return indices, not values? That single word in the problem statement changes the data structure from a Set to a Map.
3. Do you get the check-before-insert ordering right? Get it backwards and you'll pair an element with itself.
4. Do you notice the array is unsorted? If it were sorted, two pointers would beat this on space. That comparison is the interesting discussion.

Being fast isn't the goal — being clear is. A candidate who explains why the map holds value→index is rated far above one who types the answer in 20 seconds.

2. First-Principles Thought Process

Step 1 — Read the constraints

n up to 10^4.

• O(n²) → 10^8. Borderline — it would probably pass, but it's the answer they're pushing you off.
• O(n log n) → fine.
• O(n) → trivially fine.

The array is not stated to be sorted, and values span ±10^9. Both facts matter.

Step 2 — Brute force, and find the waste

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (nums[i] + nums[j] == target) return new int[]{i, j};

Now the diagnostic question: what is the inner loop doing?

At i = 0 with nums[0] = 2 and target = 9, the inner loop scans forward looking for a 7. It isn't computing anything clever — it's searching for one specific value.

Step 3 — Reframe as a lookup

Rather than "find two numbers that sum to target", rewrite it as a question asked once per element:

"For this element x, has the value target - x appeared already?"

That value has a name — the complement. And "has this exact value appeared?" is an O(1) hash lookup.

Step 4 — Decide what the map stores

Here's the step that separates understanding from memorization. A HashSet would answer "has the complement appeared?" — but the problem asks for indices, and a set doesn't record where things were.

So you need a Map<value, index>: look up by value, get back the position.

The problem statement's word "indices" is what forces Map over Set. If it asked to return the values, a Set would do.

Step 5 — Settle the ordering

Walking left to right, at each element you must decide: check first, or insert first?

Check first. Suppose nums = [3, 3] and target = 6. At i = 0, if you insert 3→0 before checking, you'd then look up the complement 3, find the entry you just added, and return [0, 0] — the same element used twice.

Checking before inserting guarantees any match came from a strictly earlier index.

Step 6 — Consider the sorted alternative

Worth raising, because it's the bridge to the next section:

If the array were sorted, you could use two pointers from both ends — O(1) space, no hash map. But sorting here would destroy the original indices, which is exactly what we must return. You'd have to pair each value with its index before sorting, which costs O(n) space anyway.

So: for the sorted variant the two-pointer method wins; for this one the hash map does. That comparison is Two Sum II.

3. Solution Paths

Approach 1 — Brute force

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) return new int[]{i, j};
        }
    }
    return new int[]{};       // unreachable — the problem guarantees a solution
}

j starts at i + 1 so no pair repeats and nothing pairs with itself.

• Time: O(n²).
• Space: O(1).

State it, give the complexity, move on.

Counter-questions on this approach

⭐ "That's O(n²). What is the inner loop searching for?"

For the single specific value target - nums[i]. Once I name it that way, the fix is obvious: searching for a known value is an O(1) hash lookup, so the inner loop can be replaced entirely.

"n is only 10⁴ — wouldn't O(n²) pass?"

Around 10^8 operations, so it's borderline rather than hopeless. But it's clearly the solution the constraints are steering me away from.

Approach 2 — Two-pass hash map

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> indexOf = new HashMap<>();
    for (int i = 0; i < nums.length; i++) indexOf.put(nums[i], i);       // pass 1

    for (int i = 0; i < nums.length; i++) {                              // pass 2
        int need = target - nums[i];
        if (indexOf.containsKey(need) && indexOf.get(need) != i) {
            return new int[]{i, indexOf.get(need)};
        }
    }
    return new int[]{};
}

Build the whole index first, then search.

The != i guard is essential. With nums = [3, 5] and target = 6, element 3 needs another 3; the map finds index 0 — itself. The guard rejects it.

• Time: O(n).
• Space: O(n).

A subtle flaw: if a value appears twice, pass 1 keeps only the last index (the second put overwrites). For [3, 3], target = 6, the map holds {3 → 1}. At i = 0: need = 3, found at index 1, and 1 != 0, so it returns [0, 1] — correct here, but you should notice the overwrite and confirm it's harmless. The one-pass version sidesteps it entirely.

Counter-questions on this approach

⭐ "If a value appears twice, your first pass keeps only the last index. Isn't that a bug?"

It's a real hazard, though not a failure here. For [3,3] with target 6 the map ends up {3 → 1}; at i = 0 the lookup finds index 1, and 1 != 0, so it returns [0,1] correctly. But it works by luck of the guarantee rather than by construction — the one-pass version removes the question entirely.

"Why do you need the != i guard?"

Without it, an element can match itself. With [3,5] and target 6, the element 3 looks for another 3, finds index 0 — itself — and returns a degenerate pair.

Approach 3 — One-pass hash map (optimal)

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();      // value -> its index

    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];

        if (seen.containsKey(need)) {                  // CHECK first
            return new int[]{seen.get(need), i};
        }
        seen.put(nums[i], i);                          // then INSERT
    }
    return new int[]{};
}

How it works. As you walk, seen holds every element strictly to the left of the current position. So asking "is the complement in seen?" asks "did a valid partner already appear?" — and because it's strictly to the left, it can't be the current element.

Trace on nums = [2, 7, 11, 15], target = 9:

Trace on nums = [3, 2, 4], target = 6:

Note step 0: need equals nums[0] itself, but seen is still empty, so there's no false match. The check-before-insert order is what makes that safe.

Trace on nums = [3, 3], target = 6:

Duplicate values handled correctly with no special case.

• Time: O(n) — one pass, O(1) average per lookup.
• Space: O(n) — worst case the map holds every element.

Counter-questions on this approach

⭐ "What happens if you insert before checking instead of after?"

You can pair an element with itself. Take [3,2,4] with target 6: at i = 0 you'd insert 3 → 0, then look up the complement 3, find the entry you just added, and return [0,0]. Checking first guarantees any match came from a strictly earlier index, which is also why duplicates like [3,3] work with no special case.

⭐ "Is the map lookup really O(1)? Justify it."

O(1) expected. If every key collided the whole algorithm would be O(n²); Java treeifies oversized buckets, capping degradation at O(log n) per operation. With Integer keys this isn't a practical concern, but "expected" is the honest word.

"Why a Map and not a Set?"

Because the problem asks for indices. A set answers "does the complement exist" but not "where". That single word in the statement is what determines the data structure.

"You're using O(n) memory. Could you get O(1) by sorting and using two pointers?"

Not without losing the answer. Sorting destroys the original indices, which are exactly what I must return. Preserving them means storing (value, index) pairs before sorting — O(n) space again — so the map is strictly better for this variant.

Comparison

4. Why the Optimal Wins

Against brute force. The brute force re-scans the array for every element — the same values examined over and over. The hash map remembers as it goes, so each element is visited once and every partner lookup is O(1). This is the archetypal O(n²) → O(n) trade in the whole section.

Against the two-pass version. Same complexity, but one pass is better for three reasons:

• It exits earlier — it can return before touching the rest of the array.
• It needs no self-pairing guard. The seen-holds-only-earlier-elements invariant makes it structurally impossible.
• It isn't affected by duplicate overwrites, because a match is found before the second copy is ever inserted.

Against sorting + two pointers. Sorting gives O(n log n) time and O(1) space — better on memory. But it destroys the indices the problem asks you to return. Preserving them means storing (value, index) pairs, which costs O(n) space and removes the advantage.

"For the unsorted, return-indices version, hashing is optimal. For the sorted, return-indices version — Two Sum II — two pointers win because the order is already given to you."

Being able to state that boundary is what the question is really probing.

Why O(n) is the floor. Every element must be examined at least once: an adversary places the answer wherever you don't look. So O(n) is optimal.

5. Java Prerequisites

HashMap basics

Map<Integer, Integer> map = new HashMap<>();
map.put(value, index);
map.containsKey(value);
map.get(value);                     // null if absent
map.getOrDefault(value, -1);        // safer default

The null-unboxing trap

int idx = map.get(missingKey);      // NullPointerException

get returns Integer, and unboxing null to int throws. In this solution the containsKey check precedes the get, so it's safe — but calling getOrDefault is the habit to build.

An alternative that avoids the double lookup:

Integer j = seen.get(need);         // one lookup
if (j != null) return new int[]{j, i};

Returning an int[]

return new int[]{i, j};             // array literal in a return statement
return new int[]{};                 // empty array — the "no answer" case
return new int[]{-1, -1};           // sentinel alternative

Autoboxing cost

Map<Integer, Integer> boxes every key and value into objects. For n = 10^4 that's fine; for tight loops on huge inputs it's a real cost. Worth mentioning, never worth hand-rolling a primitive map in an interview.

Watch == on boxed Integers

Integer a = 1000, b = 1000;
a == b;            // false! different objects
a.equals(b);       // true

Java caches Integer objects only for −128..127. Above that, == compares references. This doesn't bite in the solution above (we compare int primitives), but it bites constantly in map-heavy code. See 03.

6. Interview Communication Guide

Clarifying questions

1. "Is the array sorted?" — the highest-value question. A yes unlocks two pointers at O(1) space.
2. "Can there be duplicate values?" — affects whether you need a self-pairing guard.
3. "Is exactly one solution guaranteed, or should I handle zero or many?" — decides the return contract.
4. "Should I return indices or the values themselves?" — indices force a Map; values allow a Set.
5. "Can the same element be used twice?" — usually no; confirm.

The pitch

"The brute force checks every pair — O(n²).

But look at what the inner loop does: for the current element x, it scans for the specific value target - x. That's a search, and a hash map makes searches O(1).

Since the problem wants indices, I'll use a Map from value to index rather than a set.

One pass: at each element, compute the complement and check whether I've already seen it. If yes, return both indices. If not, record the current value and index and continue.

The important detail is the ordering — I check before inserting. That way the map only ever holds elements strictly to the left, so I can never pair an element with itself. It also handles duplicates like [3,3] correctly with no special case.

O(n) time, O(n) space."

Edge cases to raise proactively

The [3, 2, 4] case is the one to volunteer. At i = 0, target - 3 = 3, which is nums[0]. A solution that inserts before checking returns [0, 0] — wrong. Naming this unprompted proves you reasoned about the ordering rather than memorizing it.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. These are new problems, asked after your solution is accepted — not challenges to it. (Those are the counter-questions attached to each approach in §3.) ⭐ marks the most likely.

⭐ "What if the array is sorted?"

Two pointers from both ends. If the sum is too small move left up, too large move right down. O(n) time, O(1) space. It works because sorting means one comparison eliminates an entire row of candidates. That's Two Sum II.

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

Don't return early; keep scanning and collect. Deduplicate by canonicalizing each pair (smaller index first) in a Set, or sort first and skip duplicates.

"Three Sum?"

Sort, fix one element with an outer loop, then run the sorted two-pointer scan on the rest. O(n²). The dedup logic is the hard part — see 3Sum.

"What if the array doesn't fit in memory?"

If it's sorted, two pointers stream from both ends with O(1) memory. If not, external sort first, or partition by hash across machines so complements land in the same partition.

"Can you do it in O(1) space without sorting?"

Not in O(n) time. Without order to exploit and without memory to remember, you're forced back to comparing pairs — O(n²). Being able to say why a constraint is impossible is as valuable as satisfying it.

"What if the same number can be used twice?"

Then insert before checking instead of after, and [3] with target = 6 becomes valid. One line, opposite ordering — which shows you understood exactly what that ordering controls.