Two Sum Problem: Solutions in Java

Given an array and a target, return the indices of the two numbers that add to it. The optimal solution is eight lines and the interesting part is a single ordering decision inside the loop: the lookup happens before the insert, and that is what stops an element pairing with itself.

The problem

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

Two variants exist and they want different algorithms. “Return the indices, input unsorted, exactly one answer” is the hash-map problem. “Return the values, input sorted, possibly several answers” is the two-pointer problem. Confusing them is the usual reason a solution passes some tests and not others.

Brute force

static int[] bruteForce(int[] nums, int target) {
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[] { i, j };
            }
        }
    }
    return new int[0];
}

O(n²) time, O(1) space, and it is worth writing once as the reference the fast version must agree with. j = i + 1 rather than j = 0 is doing two things: it halves the work, and it makes pairing an element with itself impossible. The fast solution has to reproduce that second property some other way.

The one-pass hash map

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

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

        if (seen.containsKey(complement)) {            // look up FIRST
            return new int[] { seen.get(complement), i };
        }
        seen.put(nums[i], i);                          // then insert
    }
    return new int[0];
}

O(n) time, O(n) space. One pass, and the map holds only what has already been visited.

The lookup must come before the insert. Reverse the two lines and, with nums = [3, 5] and target = 6, the 3 is inserted, then its own complement 3 is found in the map, and the answer is [0, 0], one element used twice, the ordering is the entire guard against that, and it is why no explicit i != j check is needed.

The map is keyed by value, which is what makes the lookup O(1). It also means a repeated value overwrites its earlier index: harmless here, because the lookup happens before the overwrite, so the earlier index is still found when it matters.

The two-pass version is easier to get wrong for exactly this reason:

// two-pass — needs an explicit self-check
Map<Integer, Integer> index = new HashMap<>();
for (int i = 0; i < nums.length; i++) index.put(nums[i], i);
for (int i = 0; i < nums.length; i++) {
    Integer j = index.get(target - nums[i]);
    if (j != null && j != i) return new int[] { i, j };   // the j != i is mandatory
}

Prefer the one-pass form. It is shorter, it touches the map half as often, and the self-pairing problem cannot arise.

The two-pointer version

When the array is already sorted, no extra space is needed:

static int[] twoSumSorted(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return new int[] { left, right };
        if (sum < target) left++;
        else right--;
    }
    return new int[0];
}

O(n) time, O(1) space. The pointer moves are justified by the ordering, if the sum is too small, no pair using the current right and a smaller left can be larger, so left must increase.

Sorting an unsorted array to use this costs O(n log n), worse than the hash map, and destroys the indices, which is usually the answer being asked for. Sort only when the problem hands you sorted input or wants values back.

This is also the routine that Three Sum calls inside its outer loop, which is the real reason to be fluent in it.

Which to use

Situation	Solution	Time	Space
Unsorted, return indices	one-pass hash map	O(n)	O(n)
Already sorted, return indices or values	two pointers	O(n)	O(1)
Need all pairs	two pointers with duplicate skipping	O(n log n)	O(1)
Memory is the binding constraint	sort + two pointers	O(n log n)	O(1)

Returning every pair

The problem as usually stated promises exactly one answer. When it does not, the hash map needs a count rather than an index, and the two-pointer version needs duplicate skipping:

static List<int[]> allPairs(int[] nums, int target) {
    Arrays.sort(nums);
    List<int[]> pairs = new ArrayList<>();
    int left = 0, right = nums.length - 1;

    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            pairs.add(new int[] { nums[left], nums[right] });
            while (left < right && nums[left] == nums[left + 1]) left++;
            while (left < right && nums[right] == nums[right - 1]) right--;
            left++;
            right--;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return pairs;
}

Same three-part skip as Three Sum, one level down. The left < right guard inside each inner loop is what keeps [0,0,0,0] from walking the pointers past each other.

Overflow, and other things the tests miss

nums[left] + nums[right] overflows int when both are near Integer.MAX_VALUE, and the result wraps negative — so a pair that is far too large reads as too small and the pointer moves the wrong way. long sum = (long) nums[left] + nums[right]; fixes it.

The complement form target - nums[i] has the same exposure with a large negative target.

Three more worth a test each:

• An empty array or one element — both loops handle it via their bounds, and only because of the - 1.
• No answer exists — return an empty array or a sentinel, deliberately. Returning null pushes a NullPointerException into the caller.
• Negative numbers — no special handling is needed by either solution, which is worth confirming rather than assuming.

Why this problem is worth knowing properly

Two Sum is the base case of an entire family. Three Sum is this with an outer loop; Four Sum is two outer loops; k-sum is a recursion bottoming out here. “Subarray sum equals k” is the same complement-in-a-map idea applied to prefix sums rather than elements.

The transferable move is the one in the hash-map solution: instead of searching for a pair, walk once and ask at each element whether the thing that would complete it has already been seen. That turns a quadratic search into a linear one, and it works whenever the pairing condition can be inverted into a lookup key.

More in the algorithms guides, and Java HashMap for what the lookup actually costs.

Frequently asked questions

What is the optimal time complexity?

O(n) with a hash map, at O(n) extra space. O(n log n) with sorting and two pointers if space is the binding constraint.

Why must the lookup come before the insert?

Otherwise an element finds itself. With nums = [3, 5] and target = 6, inserting first makes 3 its own complement and returns [0, 0].

Do I need an i != j check?

Not in the one-pass version — the ordering guarantees it. The two-pass version does need it, which is one reason to prefer one pass.

What if the array contains duplicate values?

The map keyed by value overwrites the earlier index, which is harmless: the lookup runs before the overwrite, so the earlier index is still found when the pair is formed.

Should I sort and use two pointers instead?

Only if the input is already sorted, or the answer is values rather than indices. Sorting costs O(n log n) and destroys the positions.

Why do the two pointers move the way they do?

On sorted input, a sum below the target cannot be fixed by a smaller left value, so left must increase; a sum above it needs a smaller right.

How do I return all pairs instead of one?

Sort and use two pointers with duplicate skipping on both sides after each match — the same three-part skip Three Sum uses.

Can the sum overflow?

Yes, with values near Integer.MAX_VALUE. The wrap turns a too-large sum into a negative one and the pointer moves the wrong way. Sum into a long.

What should I return when there is no answer?

An empty array or a documented sentinel. null moves the failure into the caller as a NullPointerException.

How does this relate to Three Sum?

Three Sum fixes one element and runs the sorted two-pointer scan on the rest. The whole k-sum family recurses down to this base case.