Solving LeetCode’s Two Sum in Java

• Implement an efficient O(n) solution to the Two Sum problem using HashMap
• Understand how hash tables enable constant-time lookups to optimize nested loop problems
• Apply the complement pattern to transform a brute force approach into an optimal solution
• Recognize when space-time tradeoffs improve algorithmic performance

The Two Sum problem sits at the intersection of array manipulation and hash table optimization. You're given an array of integers and a target sum, and your job is to find the indices of two numbers that add up to that target. Simple enough on the surface, but the problem forces you to think about algorithmic efficiency in a way that separates naive solutions from elegant ones.

What makes Two Sum interesting isn't just finding a solution—that's trivial with nested loops. The real challenge is recognizing that you can trade a bit of memory for massive speed gains. This problem teaches you to see hash tables not just as data structures, but as tools that fundamentally change how you approach search problems. Once you internalize this pattern, you'll spot similar optimization opportunities throughout your career.

When you first see Two Sum, the instinct is to reach for nested loops. Check every pair of numbers until you find one that sums to the target:

package blog.academy.javapro;

public class TwoSumBruteForce {
    public int[] twoSum(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};
                }
            }
        }
        return new int[]{};
    }

    public static void main(String[] args) {
        TwoSumBruteForce solution = new TwoSumBruteForce();
        int[] nums = {2, 7, 11, 15};
        int target = 9;

        int[] result = solution.twoSum(nums, target);
        System.out.println("Indices: [" + result[0] + ", " + result[1] + "]");
        System.out.println("Values: " + nums[result[0]] + " + " + nums[result[1]] + " = " + target);
    }
}

This works. It's correct. But it's O(n²) time complexity, which means for an array of 10,000 elements, you're potentially making 100 million comparisons. The inner loop searches the entire remaining array for each element, doing redundant work that a smarter approach would avoid.

The problem with brute force here isn't that it fails—it's that it ignores the structure of what we're actually doing. We're searching for something specific, and hash tables were literally designed to make searching fast.

Here's the key realization: for any number in the array, there's exactly one other number that would complete the pair. If you're looking at the number 2 and your target is 9, you need to find 7. That's the complement: target - current_number.

Instead of searching through the array every time to see if that complement exists, you can store numbers in a HashMap as you go. When you encounter a new number, you first check if its complement is already in the map. If it is, you've found your pair. If not, you store the current number and move on.

The HashMap maps each number to its index in the array. This matters because the problem asks for indices, not the numbers themselves.

package blog.academy.javapro;

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

public class TwoSumOptimal {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

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

            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }

            map.put(nums[i], i);
        }

        return new int[]{};
    }

    public static void main(String[] args) {
        TwoSumOptimal solution = new TwoSumOptimal();
        int[] nums = {2, 7, 11, 15};
        int target = 9;

        int[] result = solution.twoSum(nums, target);
        System.out.println("Indices: [" + result[0] + ", " + result[1] + "]");
        System.out.println("Values: " + nums[result[0]] + " + " + nums[result[1]] + " = " + target);
    }
}

Below you can see the visualization of how this algorithm processes the array step by step, showing the state of the HashMap at each iteration.

Below you can see the visualization of how this algorithm processes the array step by step, showing the state of the HashMap at each iteration.

The algorithm makes a single pass through the array. At each position, you're asking two questions:

1. Have I already seen the complement of this number?
2. If not, let me remember this number for later.

The HashMap's O(1) average-case lookup time means checking for the complement is essentially free. You've transformed the inner loop's linear search into a constant-time operation. That's the difference between O(n²) and O(n).

The order matters here. You check the map before adding the current number. This prevents the algorithm from finding the same element twice. If you're at index 3 looking at the number 5, and the target is 10, you don't want to find the same 5 at index 3 as your complement. By checking first and adding after, you ensure you're always looking at previously processed elements.

The HashMap stores <Integer, Integer> pairs where the key is the number from the array and the value is its index. When you find a complement, map.get(complement) returns the index where that complement was found, and i gives you the current index. The problem guarantees exactly one solution exists, so you can return immediately when you find the pair.

The return type is int[] because you need to return two indices. Java arrays are objects, so return new int[] {map.get(complement), i} creates a new array on the heap with the two indices. The returned array always has the smaller index first because you store elements as you encounter them.

package blog.academy.javapro;

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

public class TwoSumWithValidation {
    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            throw new IllegalArgumentException("Array must contain at least two elements");
        }

        Map<Integer, Integer> map = new HashMap<>();

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

            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }

            map.put(nums[i], i);
        }

        throw new IllegalArgumentException("No two sum solution exists");
    }

    public static void main(String[] args) {
        TwoSumWithValidation solution = new TwoSumWithValidation();

        // Test case 1: Standard case
        int[] nums1 = {2, 7, 11, 15};
        int[] result1 = solution.twoSum(nums1, 9);
        System.out.println("Test 1: " + Arrays.toString(result1));

        // Test case 2: Negative numbers
        int[] nums2 = {-3, 4, 3, 90};
        int[] result2 = solution.twoSum(nums2, 0);
        System.out.println("Test 2: " + Arrays.toString(result2));

        // Test case 3: Same number appears twice
        int[] nums3 = {3, 2, 4};
        int[] result3 = solution.twoSum(nums3, 6);
        System.out.println("Test 3: " + Arrays.toString(result3));

        // Test case 4: Duplicate values where sum equals target
        int[] nums4 = {3, 3};
        int[] result4 = solution.twoSum(nums4, 6);
        System.out.println("Test 4: " + Arrays.toString(result4));
    }
}

Duplicate numbers in the array don't break the algorithm. The HashMap will overwrite the old index with the new one when you encounter the same number again, but that's fine. If the target requires using the same number twice (like [3, 3] with target 6), the algorithm handles it correctly because you check for the complement before storing the current element.

Negative numbers work without modification. The complement calculation target - nums[i] produces the correct value regardless of sign. If your array is [-3, 4, 3, 90] and your target is 0, when you reach index 2 (value 3), the complement is -3, which you've already stored at index 0.

Integer overflow is theoretically possible if your numbers are near Integer.MAX_VALUE or Integer.MIN_VALUE, but typical interview problems don't test this boundary. In production code, you'd need to consider whether to use long for the complement calculation or add explicit overflow checks.

The brute force solution uses O(1) space but takes O(n²) time. The HashMap solution uses O(n) space but only takes O(n) time. You're storing up to n elements in the map, which costs memory, but you've eliminated an entire dimension of iteration.

This is a classic space-time tradeoff, and in this case, the trade is absolutely worth it. Modern systems have plenty of memory, but CPU cycles and user patience are limited. Going from quadratic to linear time complexity is a massive win that justifies the memory cost.

The HashMap's average-case O(1) operations come from Java's implementation of chaining to handle hash collisions. Under the hood, each bucket in the HashMap can hold multiple entries, stored in a linked list (or a tree structure after a certain threshold in Java 8+). For typical inputs, collisions are rare enough that lookups remain effectively constant time.

The Two Sum pattern—using a hash table to remember what you've seen and checking for complements—appears throughout algorithm design. Any time you're searching for pairs, triplets, or subsets with specific properties, consider whether a HashMap can eliminate nested loops.

Three Sum extends this approach by fixing one element and running Two Sum on the remaining array. Four Sum follows the same principle. Subarray sum problems use similar techniques with prefix sums stored in hash tables. The core insight—trade space for speed by remembering previous values—applies broadly.

You'll see this pattern in real systems too. Database query optimization, caching strategies, and memoization all rely on the same principle: store computed results so you don't have to recompute them. The Two Sum solution is a microcosm of how hash-based data structures enable efficient search operations across computer science.

The Two Sum problem demonstrates how the right data structure transforms an algorithm's performance. The brute force nested loop approach is intuitive but scales poorly, checking every possible pair in O(n²) time. By introducing a HashMap to store values as you traverse the array, you can check for complements in constant time, reducing the overall complexity to O(n).

The solution relies on a single pass through the array. At each element, you calculate what number would complete the pair, check if you've already seen it, and store the current number for future lookups. The HashMap maps numbers to their indices, which lets you return the positions rather than the values themselves.

This pattern of using hash tables to remember previous elements appears throughout algorithmic problem-solving. Anytime you're searching for relationships between elements—pairs that sum to a target, elements that satisfy a condition, duplicates within a window—consider whether a HashMap can replace a nested loop. The space-time tradeoff is usually favorable: a linear amount of extra memory buys you an exponential reduction in time complexity.

The Two Sum solution also highlights how problem constraints shape your approach. The guarantee of exactly one solution means you can return immediately when you find it, without worrying about multiple valid answers. The requirement to return indices rather than values influences how you structure your HashMap. Understanding these details matters because real-world programming rarely involves solving problems in isolation—you're always working within constraints that guide your design choices.