Two Sum (Unsorted) in Java: Solution, Explanation & Practice

Find two numbers that add up to target using HashMap

Problem summary

Given an unsorted array and target, find two numbers that add up to target. Use HashMap for O(n) solution.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        
        // Store complement in HashMap
        // For each num, check if (target - num) exists
        // Print: Indices: 0, 1
    }
}

Expected output and test cases

[2,7,11,15], target=9
```
Indices: 0, 1
```
[3,2,4], target=6
```
Indices: 1, 2
```
[3,3], target=6
```
Indices: 0, 1
```

Hints

For each number, its complement is target - number
Store each number with its index in HashMap
Before storing, check if complement already exists
If yes, we found our pair!

Validated solution

Reveal Java solution

import java.util.HashMap;
import java.util.Map;

public class Main {
    static int[] twoSum(int[] numbers, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            Integer match = seen.get(target - numbers[i]);
            if (match != null) return new int[] {match, i};
            seen.put(numbers[i], i);
        }
        return new int[] {-1, -1};
    }
    public static void main(String[] args) {
        int[] indices = twoSum(new int[] {2, 7, 11, 15}, 9);
        System.out.println("Indices: " + indices[0] + ", " + indices[1]);
    }
}

How to approach the problem

A hash map converts the two-sum complement check from repeated searching into an expected constant-time lookup. Check before recording the current number so one array slot cannot fulfill both roles.

Approach

For each number, derive the needed complement.
Look for that complement among earlier indices.
Store the current value and index only after no match.

Time and space complexity

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

Edge cases to test

Equal values need two occurrences to form a pair.
The fallback here is {-1, -1}; another API might return Optional.

Common mistakes

Returning two values when the problem asks for indices.
Overwriting an earlier index without thinking through the duplicate policy.

Follow-up challenge

Solve two sum on a sorted array with two pointers and compare memory use.

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler