A checkout service is given a list of unpaid invoice amounts and a credit memo. The question is not “do any two lines exist” — accounting needs the indexes so it can mark those two invoices. The first version nested a scan: for each i, every j > i. A dozen invoices in the staging tenant returned in milliseconds. Eighty thousand invoices in production were still looping when the request timed out.

Two Sum asks for two indices whose values add to a target. An array already gives a[i] for free. Nested search uses that and still pays O(n²). Sorting would make a two-pointer pass legal, but sorting permutes the indexes you were asked to return.

This is an interview writeup, not a layout lecture. The hash table post owns buckets and collisions. Here we only care about storing what we have already seen so the complement is a lookup, not a restart.

The problem

Given an int[] nums and an int target, return the two distinct indices i and j such that nums[i] + nums[j] == target. Exactly one solution exists. You may not use the same index twice. Order of the two indices does not matter.

nums = [2, 7, 11, 15], target = 9  →  [0, 1]   because 2 + 7 = 9
nums = [3, 2, 4],      target = 6  →  [1, 2]   because 2 + 4 = 6
nums = [3, 3],         target = 6  →  [0, 1]

Note: If the prompt asked only “does a pair exist?” on already sorted data, opposite-end two pointers would be the cheaper procedure. This prompt asks for indices on an unordered array. Sorting first means you must carry the original index along, then unsort. A map does not need that dance.

Nested search is the honest brute force

Every unordered pair is visited once. Correct. Quadratic.

int[] twoSumNested(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 };
            }
        }
    }
    throw new IllegalArgumentException("no pair");
}

At n = 20 this is a rounding error. At n in the tens of thousands you paid a nested scan for a question a hash table answers in expected constant time per index: have I already seen target - nums[i]?

One pass: store the complement’s partner

Walk left to right. Before you look at nums[i], the map holds every earlier value and the index where it sat.

  • Let need = target - nums[i].
  • If need is already a key, you are done: that stored index and i.
  • Otherwise record nums[i] → i and continue.

You never restart a scan from index 0. You never sort. Same index cannot pair with itself because you look up before you insert the current value.

nums = [2, 7, 11, 15]   target = 9

i=0  value=2   need=7    map {}           miss, put 2 → 0
i=1  value=7   need=2    map {2:0}        hit, return [0, 1]

The Java is that walk:

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        Integer partner = seen.get(need);
        if (partner != null) {
            return new int[] { partner, i };
        }
        seen.put(nums[i], i);
    }
    throw new IllegalArgumentException("no pair");
}

Time is expected O(n) — one pass, one expected-O(1) lookup and put per index. Space is O(n) for the map. Worst-case hash degeneration is the same story the hash-table post already told; do not re-lecture it at the whiteboard unless they ask.

Note: Look up before you insert. If you put first, a lone 4 with target 8 finds itself (need is 4, the map already holds index 0) and returns the same index twice. The lookup-first order refuses that pair and still accepts [3, 3] with target 6 on the second index.

What interviewers usually poke next

  • Sorted input, existence only. Then two pointers, O(1) extra space, and you can say why the map is the wrong bill.
  • Return all pairs, not one. Deduplicate values, or collect indices into a list per value. The one-solution guarantee goes away; say so.
  • Overflow. need = target - nums[i] is fine for int in Java (wrap is defined). If they switch the type to a wider sum, name that.
  • Null / empty / fewer than two elements. The prompt promised a solution. In production you would reject; at the board, ask.

You are done with this problem when you can say, out loud, why the nested scan is correct, why sorting fights the index requirement, and why the map lookup happens before the put.