Two Number Sum

Two Number Sum is the first problem in most interview prep courses, and it is worth more than the five minutes it takes to solve. It has three reasonable answers with genuinely different trade-offs, and being able to lay all three out and then justify a choice is the actual skill being tested.

The problem

Given a non-empty array of distinct integers and a target sum, return two numbers from the array that add up to the target, in any order. Return an empty array if no pair exists. The two numbers must be at different positions — you cannot add a value to itself.

array = [3, 5, -4, 8, 11, 1, -1, 6], target = 10
  -> [-1, 11]        11 + (-1) = 10

array = [4, 6], target = 10   -> [4, 6]
array = [4, 6], target = 11   -> []
array = [3], target = 6       -> []   one element cannot pair with itself

Note "distinct" — it is a real simplification, and it is worth asking whether it holds. It removes every duplicate-handling concern, which is exactly what makes the harder cousins of this problem harder.

First attempt: check every pair

The honest starting point. Say it, write it, then improve it — an interviewer wants to see you establish a correct baseline before optimising.

public static int[] twoNumberSum(int[] array, int targetSum) {
    // Start the inner loop at x + 1, not 0. Every pair is then visited exactly
    // once, and no element can ever pair with itself.
    for (int x = 0; x < array.length; x++) {
        for (int y = x + 1; y < array.length; y++) {
            if (array[x] + array[y] == targetSum) {
                return new int[] { array[x], array[y] };
            }
        }
    }

    return new int[0];
}

Starting the inner loop at x + 1 rather than 0 matters twice over. It halves the work, and it removes the need for an if (x == y) continue; guard — the constraint that the two numbers come from different positions is enforced by the loop bounds instead of by a check you might forget.

Time O(n²), space O(1).

Second attempt: sort, then close in from both ends

Once the array is sorted, a pair that sums too low can only be fixed by taking a larger small number, and a pair that sums too high by taking a smaller large number. So two pointers walking inwards never miss the answer, and neither ever needs to go back.

public static int[] twoNumberSum(int[] array, int targetSum) {
    Arrays.sort(array);          // note: this reorders the CALLER's array

    int left = 0;
    int right = array.length - 1;

    while (left < right) {
        int sum = array[left] + array[right];

        if (sum == targetSum) {
            return new int[] { array[left], array[right] };
        } else if (sum < targetSum) {
            left++;              // need a bigger number
        } else {
            right--;             // need a smaller number
        }
    }

    return new int[0];
}

left < right, not left <= right. Allowing them to meet would let a single element pair with itself.

Arrays.sort(array) mutates the input. That is a side effect the caller did not ask for, and in production it is the kind of thing that causes a bug three functions away. Say it out loud, and offer array.clone() if the caller needs the original order — at the cost of the O(1) space that was this approach's whole selling point.

Time O(n log n) from the sort, space O(1). This is the answer when memory matters more than speed.

Third attempt: remember what you have seen

The nested loop keeps asking the same question — "is target - array[x] in this array?" — and membership questions are what hash sets are for.

public static int[] twoNumberSum(int[] array, int targetSum) {
    Set<Integer> seen = new HashSet<>();

    for (int num : array) {
        int match = targetSum - num;

        if (seen.contains(match)) {   // check BEFORE inserting
            return new int[] { match, num };
        }
        seen.add(num);
    }

    return new int[0];
}

A Set, not a Map — nothing here needs a value alongside the key. (If you need indices rather than values, that is when a Map<Integer, Integer> earns its place; see below.)

Check membership before inserting. Insert first and an element can match itself: with target = 10 and a 5 in the array, the 5 would already be in the set when you look for its partner and you would wrongly return [5, 5]. That is the single most common bug in this problem.

Time O(n), space O(n). The answer when speed matters more than memory, and the one to reach for by default.

Python

def two_number_sum(array: list[int], target_sum: int) -> list[int]:
    seen = set()

    for num in array:
        match = target_sum - num

        if match in seen:          # check before adding
            return [match, num]
        seen.add(num)

    return []

Returning indices instead of values

A very common follow-up, and it is the version LeetCode 1 actually asks for. Swap the set for a map from value to index, and note that the sorting approach is now essentially unusable — sorting destroys the positions the question is asking about.

public static int[] twoNumberSumIndices(int[] array, int targetSum) {
    Map<Integer, Integer> seen = new HashMap<>();   // value -> index

    for (int i = 0; i < array.length; i++) {
        Integer j = seen.get(targetSum - array[i]);

        if (j != null) {
            return new int[] { j, i };
        }
        seen.put(array[i], i);
    }

    return new int[0];
}

Choosing between them

Approach	Time	Space	Mutates input
Every pair	`O(n²)`	`O(1)`	no
Sort + two pointers	`O(n log n)`	`O(1)`	yes
Hash set	`O(n)`	`O(n)`	no

There is no single right answer, which is the point. Default to the hash set. Choose two pointers when memory is tight, when the array is already sorted (the sort cost vanishes and it becomes O(n) in O(1) space, beating the hash set outright), or when you need every pair rather than just one.

Where this leads

The two-pointer version is the one worth internalising even though it is usually not the answer here, because it is the foundation of the harder problems:

Three Number Sum — fix one element, then two-pointer the rest. There is no hash-set solution that is as clean.
LeetCode 15, 3Sum — the same thing with duplicates allowed, which is where all the real difficulty lives.
Four Number Sum — two nested loops around a hash map of pair sums.

Source code on GitHub

What the interviewer is checking

That you give the brute force first, then improve it — not that you jump straight to the hash set with no reasoning.
That you check the set before inserting, so no element pairs with itself.
That you notice sorting mutates the caller's array, and say so.
That you can compare all three on time and space and defend a choice, rather than asserting one is "the optimal solution".
Arrays of length 0 and 1, and the case where no pair exists.
Whether you asked what happens if the values are not distinct.