Two Sum Problem Using Hashing — The Fast O(n) Solution Explained

The Two Sum problem is probably the most famous coding interview question in the world. It shows up at Google, Amazon, Meta, and practically every tech company that cares about algorithmic thinking. But its fame isn't just because interviewers are lazy — it's because the problem perfectly exposes whether a candidate knows how to trade memory for speed, which is one of the most important skills in software engineering.

The problem itself sounds almost too simple: given a list of numbers and a target value, find the two numbers in the list that add up to the target. The naive approach — check every pair — works, but it's painfully slow for large inputs. The hashing approach cuts that time dramatically by remembering what you've already seen as you walk through the list just once.

By the end of this article you'll understand exactly why hashing makes this problem fast, be able to write the solution from memory, know the exact edge cases that trip up beginners, and have confident answers ready for the three follow-up questions interviewers love to ask.

The Brute Force Approach — And Why It Falls Apart

Before we reach for the elegant solution, let's fully understand the problem and the obvious first attempt. You're given an array of integers — say [2, 7, 11, 15] — and a target number, say 9. Your job is to find which two numbers sum to 9. In this case it's 2 and 7, sitting at index 0 and index 1.

The most natural thing a beginner does is use two nested loops: pick the first number, then loop through every remaining number to see if they sum to the target. This works correctly — but think about what happens when your array has 10,000 elements. For each of the 10,000 numbers, you scan up to 9,999 others. That's roughly 100 million comparisons. On a large dataset this gets brutally slow.

In computer science we describe this cost as $O(n^2)$ — pronounced 'O of n squared'. It means the work grows with the square of the input size. Double the input, quadruple the work. This is the core pain point that hashing solves, and understanding this pain makes the solution feel like a genuine breakthrough rather than a magic trick.

package io.thecodeforge.algorithms;

public class TwoSumBruteForce {

    /**
     * Finds the indices of two numbers that add up to the target.
     * Uses two nested loops — simple but slow: O(n^2) time complexity.
     *
     * @param numbers  the input array of integers
     * @param target   the value we want two numbers to sum to
     * @return         an int array with the two indices, or empty array if not found
     */
    public static int[] findTwoSumBruteForce(int[] numbers, int target) {
        // Outer loop: pick each number as the first candidate
        for (int i = 0; i < numbers.length; i++) {
            // Inner loop: compare it against every number that comes after it
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{};
    }

    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        int[] result = findTwoSumBruteForce(numbers, target);
        if (result.length == 2) {
            System.out.println("Indices: [" + result[0] + ", " + result[1] + "]");
        }
    }
}

How Hashing Turns an O(n²) Problem Into O(n)

Here's the key insight: when you're standing at any number in the array, you already know exactly what its partner needs to be. If the current number is 7 and the target is 9, the partner must be 2. You don't need to search for it — you just need to check whether you've already seen it.

A HashMap is the perfect tool for this. Think of it as an instant-lookup notebook. As you walk through the array, you write each number and its index into the notebook. When you land on a new number, before writing it down, you flip open the notebook and ask: 'Is the complement (target minus current number) already in here?' If yes — you're done. If no — write the current number down and move on.

This means you only walk through the array once. One pass. The HashMap lookup happens in $O(1)$ — constant time — regardless of how many entries are in the map. So the total work is $O(n)$: you do a fixed amount of work per element, and there are n elements. That's the trade-off: you use a little extra memory (the HashMap) to eliminate the entire inner loop.

This idea — using a data structure to trade memory for speed — is one of the most reusable patterns in all of computer science.

package io.thecodeforge.algorithms;

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

public class TwoSumHashing {

    /**
     * Finds the indices of two numbers that add up to the target.
     * Uses a HashMap for O(1) average lookups — overall O(n) time complexity.
     *
     * @param numbers  the input array
     * @param target   the target sum
     * @return         indices of the two numbers
     */
    public static int[] findTwoSum(int[] numbers, int target) {
        // Stores { value -> index }
        Map<Integer, Integer> seen = new HashMap<>();

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

            // Check if our partner was already encountered
            if (seen.containsKey(complement)) {
                return new int[]{seen.get(complement), i};
            }

            // Store current value and index for future partners to find
            seen.put(current, i);
        }

        return new int[]{}; // No solution found
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int[] result = findTwoSum(nums, 9);
        System.out.println("Found at: [" + result[0] + ", " + result[1] + "]");
    }
}

What's Actually Happening Inside the HashMap — A Visual Walkthrough

Seeing code is one thing; watching it execute step-by-step is how it really sticks. Let's trace through numbers = [2, 7, 11, 15] with target = 9 manually, as if we're the program.

Step 1: currentNumber = 2. Complement = 9 - 2 = 7. Is 7 in seenNumbers? No — map is empty. Store {2 → 0}. Move on.

Step 2: currentNumber = 7. Complement = 9 - 7 = 2. Is 2 in seenNumbers? YES — it's at index 0! Return [0, 1]. Done.

We never even looked at 11 or 15. The algorithm stopped the moment it found the answer. Now contrast that with brute force, which would have checked every single pair in the worst case.

The HashMap is the reason we can ask 'have I seen X?' and get a yes/no answer almost immediately, without scanning anything. Internally, Java's HashMap converts the key (a number like 2) into a bucket position using a hash function, making retrieval constant-time. You don't need to understand the internal math right now — just trust that containsKey() and get() are both $O(1)$ operations.

package io.thecodeforge.algorithms;

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

public class TwoSumWithTrace {
    public static int[] findTwoSumWithTrace(int[] numbers, int target) {
        Map<Integer, Integer> seenNumbers = new HashMap<>();
        System.out.println("Target: " + target);

        for (int i = 0; i < numbers.length; i++) {
            int num = numbers[i];
            int complement = target - num;
            System.out.printf("Step %d: Value=%d, Needs=%d. Seen? %s\n", 
                              i+1, num, complement, seenNumbers.containsKey(complement));

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

    public static void main(String[] args) {
        findTwoSumWithTrace(new int[]{2, 7, 11, 15}, 9);
    }
}

Frequently Asked Questions