Two Sum with HashMap in Java: Solution, Explanation & Practice

Problem summary

Use HashMap to find two numbers that add up to target in O(n) time.

Starter code

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9; // Test case 1
        
        // Find pair using HashMap
        // Print: Indices: <i>, <j>
    }
}

Expected output and test cases

• 2 + 7 = 9

  Indices: 0, 1

• Different pair

  Indices: 1, 2

• No valid pair

  No pair found

Hints

1. Store complement (target - num) in map
2. Check if current num is in map
3. Map value stores index

Validated solution

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

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

How to approach the problem

Store each earlier value with its index. Before storing the current value, look up the complement; this ordering guarantees a pair uses two different positions.

Approach

1. Create a value-to-index map.
2. Look up target - current value first.
3. Store the current value only when no match exists.

Time and space complexity

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

Edge cases to test

• Duplicate values such as 3 and 3 work because the first index is stored before the second is checked.
• No matching pair returns null in this small exercise API.

Common mistakes

• Checking after inserting and pairing an item with itself.
• Returning values when the contract asks for indices.

Follow-up challenge

Return all unique index pairs while avoiding duplicate pairs.

Related Collections exercises

• Practice Simple LRU Cache in Java
• Practice Priority Queue with Custom Order in Java
• Practice First Unique Element in Java

Practice all Collections exercises · Run this idea in the Java compiler