Two Sum in Java: Why a HashMap Beats the Nested Loop

Two Sum is usually the very first problem anyone solves in Data Structures and Algorithms, which is exactly why it's easy to underrate. It takes about two minutes to write something that passes every test case. It takes a lot longer to notice the one-line ordering mistake hiding inside the fast solution — the kind of mistake that doesn't show up until someone hands you a test case you didn't think to write yourself.

What the problem is actually asking

Two Sum is usually the very first problem anyone solves in Data Structures and Algorithms, which is exactly why it's easy to underrate. It takes about two minutes to write something that passes every test case. It takes a lot longer to notice the one-line ordering mistake hiding inside the fast solution — the kind of mistake that doesn't show up until someone hands you a test case you didn't think to write yourself.

The problem, stated plainly: given an array of integers nums and an integer target, return the indices of the two numbers that add up to target.

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

nums[0] + nums[1] = 2 + 7 = 9

Two details are easy to skim past and both matter. It asks for indices, not values — which turns out to be the reason the whole solution works the way it does. And you're told there's exactly one valid answer, so once you find a pair, you're done; there's no need to keep looking for a better one.

The first instinct: check every pair

Almost everyone reaches for the same idea first, and it's a reasonable one. Pick a number, compare it against every number after it, and see if any pair adds up to the target.

class Solution {
    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[]{};
    }
}

It's correct, and it's easy to reason about. It's also doing roughly n²/2 comparisons, because for every element it's willing to re-scan the entire rest of the array to check whether a partner exists. That's fine at four elements. It stops being fine once an interviewer asks the question they always ask: what if there were a hundred thousand?

The idea that makes it fast: stop searching, start remembering

The nested loop keeps asking the same expensive question — "does some other number in this array complete the pair I'm holding?" — and answering it by looking at the whole array again. The faster solution asks a cheaper question instead: "have I already seen the one number that would complete this pair?"

That one number has a name. It's the complement, and for any element you're standing on, there's exactly one value in the universe that finishes the pair:

complement = target - currentNumber

If you've kept a record of every number you've already walked past — value mapped to the index you saw it at — then answering "have I seen the complement" is a single lookup instead of a second loop. A HashMap is that record, and a hash lookup costs the same whether you've stored ten numbers or ten million.

Walking through it

The same example, traced one step at a time:

nums = [2, 7, 11, 15]
target = 9
map = {}

At index 0, the current number is 2. Its complement is 9 − 2 = 7. The map is empty, so 7 isn't there — store 2 at index 0 and move on.

At index 1, the current number is 7. Its complement is 9 − 7 = 2. The map now holds {2 → 0}, and 2 is right there. Return [0, 1]. Done.

The full solution is short enough to hold in your head in one pass:

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{};
    }
}

The one-line order that decides whether it's correct

Here's the part that separates people who've understood this solution from people who've memorised it. Look closely at the loop: the code checks whether the complement exists before it stores the current number. That ordering isn't a style choice. Swap it, and the function breaks on an input that looks perfectly ordinary.

Take nums = [3, 3] with target = 6.

Check first, and the map only ever contains numbers from strictly earlier positions — so a match is always two different elements, and [3, 3] correctly returns [0, 1]. Store first, and by the time index 1 asks "have I seen 3?", the answer is yes — because index 0 already put itself there. The function returns [0, 0], using the same element twice, which the problem explicitly forbids.

This is also the quiet reason the problem asks for indices instead of values. Values would be ambiguous the moment two elements are equal. Indices never are.

What it costs

The trade is explicit and worth naming out loud: you give up O(1) space and buy back an entire factor of n in time. For a small array the difference is invisible. For a large one, it's the difference between a solution that finishes and one that doesn't.

Saying it out loud

Knowing the code isn't quite the same as being able to explain it under pressure, so it's worth rehearsing the explanation as a sentence, not just the syntax:

I first thought of the brute-force approach with two nested loops, but that's O(n²). To optimize it, I use a HashMap that stores each number alongside its index. For every element, I calculate the complement as target minus the current number, and check whether it's already in the map before I store anything. If it is, I return the stored index and the current index. If it isn't, I store the current number and move on. Checking before storing is what stops an element from pairing with itself. This runs in O(n) time with O(n) extra space.

That last sentence about checking before storing is the one people forget to say — and it's usually the one that tells an interviewer you understand the solution rather than having recited it.

What Two Sum is really testing

Two Sum gets used as the opening problem in almost every interview prep list, and it's tempting to treat it as a formality — something to clear quickly on the way to harder questions. It's more useful than that if you let it be. It's a small, contained rehearsal of a habit that shows up in every problem after it: get a working solution first, then ask what it's costing you, then look for the piece of information you're computing more than once. Here, that piece of information was "have I seen this number before," and remembering the answer instead of re-deriving it is what turned a quadratic scan into a single pass.

The HashMap isn't the lesson. Noticing that the expensive part of your solution is a question you've already answered once — that's the lesson, and Two Sum is just the smallest possible example of it.

Working through DSA fundamentals like this one? The archive has free PDF notes on data structures, algorithms, and computer science fundamentals — no account needed.