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²) — 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.
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 firstIndex = 0; firstIndex < numbers.length; firstIndex++) { // Inner loop: compare it against every number that comes after it // We start at firstIndex + 1 to avoid using the same element twice for (int secondIndex = firstIndex + 1; secondIndex < numbers.length; secondIndex++) { // Check if these two numbers add up to our target if (numbers[firstIndex] + numbers[secondIndex] == target) { // Found it — return the two indices return new int[]{firstIndex, secondIndex}; } } } // If we exhausted all pairs and found nothing, return an empty array 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 found: [" + result[0] + ", " + result[1] + "]"); System.out.println("Values: " + numbers[result[0]] + " + " + numbers[result[1]] + " = " + target); } else { System.out.println("No two numbers sum to the target."); } } }
Values: 2 + 7 = 9
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.
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) lookups — overall O(n) time complexity. * * Strategy: For each number, calculate what its complement must be * (complement = target - currentNumber), then check if we've seen * that complement before. If yes, we found our pair! * * @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[] findTwoSumHashing(int[] numbers, int target) { // This map stores: { number -> index where we saw it } // e.g. if numbers[0] = 2, we store { 2 -> 0 } Map<Integer, Integer> seenNumbers = new HashMap<>(); for (int currentIndex = 0; currentIndex < numbers.length; currentIndex++) { int currentNumber = numbers[currentIndex]; // What number, when added to currentNumber, gives us the target? // That's the complement. If target=9 and currentNumber=7, complement=2. int complement = target - currentNumber; // Has the complement already been seen earlier in the array? if (seenNumbers.containsKey(complement)) { // Yes! Retrieve the index where we saw the complement int complementIndex = seenNumbers.get(complement); // Return both indices. complementIndex came earlier, so it goes first. return new int[]{complementIndex, currentIndex}; } // Complement not seen yet — record the current number and its index // so future numbers can find it as their complement seenNumbers.put(currentNumber, currentIndex); } // Walked the entire array, no valid pair found return new int[]{}; } public static void main(String[] args) { // --- Test Case 1: Basic example --- int[] numbers1 = {2, 7, 11, 15}; int target1 = 9; int[] result1 = findTwoSumHashing(numbers1, target1); System.out.println("Test 1 — Indices: [" + result1[0] + ", " + result1[1] + "]"); System.out.println(" Values: " + numbers1[result1[0]] + " + " + numbers1[result1[1]] + " = " + target1); // --- Test Case 2: Answer is not at the start --- int[] numbers2 = {3, 5, -4, 8, 11, 1, -1, 6}; int target2 = 10; int[] result2 = findTwoSumHashing(numbers2, target2); System.out.println("\nTest 2 — Indices: [" + result2[0] + ", " + result2[1] + "]"); System.out.println(" Values: " + numbers2[result2[0]] + " + " + numbers2[result2[1]] + " = " + target2); // --- Test Case 3: No valid pair exists --- int[] numbers3 = {1, 2, 3, 4}; int target3 = 100; int[] result3 = findTwoSumHashing(numbers3, target3); if (result3.length == 0) { System.out.println("\nTest 3 — No pair found that sums to " + target3); } // --- Test Case 4: Negative numbers --- int[] numbers4 = {-3, 4, 3, 90}; int target4 = 0; int[] result4 = findTwoSumHashing(numbers4, target4); System.out.println("\nTest 4 — Indices: [" + result4[0] + ", " + result4[1] + "]"); System.out.println(" Values: " + numbers4[result4[0]] + " + " + numbers4[result4[1]] + " = " + target4); } }
Values: 2 + 7 = 9
Test 2 — Indices: [4, 6]
Values: 11 + -1 = 10
Test 3 — No pair found that sums to 100
Test 4 — Indices: [0, 2]
Values: -3 + 3 = 0
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 the pair (2,7), found it, and returned — but would have also checked (2,11), (2,15), (7,11), (7,15), (11,15) if the answer wasn't at the front. In the worst case, brute force checks every single pair.
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.
import java.util.HashMap; import java.util.Map; /** * Same algorithm as TwoSumHashing.java, but with detailed trace logging * so you can watch exactly what the HashMap contains at each step. * Great for learning — remove the print statements in production. */ public class TwoSumWithTrace { public static int[] findTwoSumWithTrace(int[] numbers, int target) { Map<Integer, Integer> seenNumbers = new HashMap<>(); System.out.println("Target: " + target); System.out.println("-----------------------------"); for (int currentIndex = 0; currentIndex < numbers.length; currentIndex++) { int currentNumber = numbers[currentIndex]; int complement = target - currentNumber; System.out.println("Step " + (currentIndex + 1) + ": currentNumber=" + currentNumber + ", complement=" + complement); System.out.println(" seenNumbers map: " + seenNumbers); if (seenNumbers.containsKey(complement)) { int complementIndex = seenNumbers.get(complement); System.out.println(" ✓ Found complement " + complement + " at index " + complementIndex + "! Returning [" + complementIndex + ", " + currentIndex + "]"); return new int[]{complementIndex, currentIndex}; } // Complement not in map yet — record current number for future use seenNumbers.put(currentNumber, currentIndex); System.out.println(" → Stored " + currentNumber + " in map."); } System.out.println("No valid pair found."); return new int[]{}; } public static void main(String[] args) { int[] numbers = {2, 7, 11, 15}; int target = 9; findTwoSumWithTrace(numbers, target); } }
-----------------------------
Step 1: currentNumber=2, complement=7
seenNumbers map: {}
→ Stored 2 in map.
Step 2: currentNumber=7, complement=2
seenNumbers map: {2=0}
✓ Found complement 2 at index 0! Returning [0, 1]
| Aspect | Brute Force (Nested Loops) | Hashing (HashMap) |
|---|---|---|
| Time Complexity | O(n²) — grows with square of input | O(n) — grows linearly with input |
| Space Complexity | O(1) — no extra data structure | O(n) — HashMap stores up to n entries |
| Passes through array | Two nested passes | Single pass |
| Works with duplicates? | Yes | Yes (last index of duplicate is stored) |
| Works with negatives? | Yes | Yes — HashMap handles any integer key |
| Code complexity | Simple to read and write | Slightly more code, but still readable |
| Best use case | Tiny arrays where memory matters | Any real-world input size |
| 10,000 element array | ~50 million comparisons | ~10,000 comparisons |
🎯 Key Takeaways
- The core insight is complement recognition: instead of searching for a partner, calculate exactly what the partner must be (target - currentNumber), then check if it exists — turning a search into an instant lookup.
- HashMap's containsKey() and get() both run in O(1) average time, which is what makes the single-pass O(n) solution possible — without that, you'd need a nested loop.
- Always insert into the map AFTER checking for the complement — this single ordering decision prevents a number from falsely matching itself and correctly handles duplicate values in the array.
- The Two Sum pattern generalises beyond this exact problem: any time you're searching for a complement, a pair, or a previously-seen value, reach for a HashMap first — it's one of the most reusable patterns in algorithm design.
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Inserting into the map before checking the complement — If you call seenNumbers.put(currentNumber, currentIndex) before seenNumbers.containsKey(complement), a number can match itself as its own complement. For example, with numbers=[6] and target=12, the number 6 would find itself in the map and incorrectly return [0, 0]. Fix: always check containsKey first, then put.
- ✕Mistake 2: Forgetting that the same number can appear twice in the array — For input [3, 3] with target=6, the correct answer is indices [0, 1]. The insert-after-check pattern handles this correctly: when you reach the second 3, the first 3 is already in the map, so the complement check succeeds. But if you pre-populate the map before the loop (a common shortcut attempt), the second 3 would overwrite the first, and you'd lose index 0. Never pre-populate — build the map as you go.
- ✕Mistake 3: Returning the values instead of the indices — The Two Sum problem (in its classic LeetCode form) asks for indices, not the numbers themselves. A common mistake is returning new int[]{complement, currentNumber} instead of new int[]{complementIndex, currentIndex}. Always re-read what the problem asks for before writing the return statement, and use clearly named variables like complementIndex so you never confuse a value for an index.
Interview Questions on This Topic
- QCan you walk me through the time and space complexity of your HashMap solution and explain the trade-off you're making compared to the brute force approach?
- QWhat happens in your solution if the input array contains duplicate numbers — say [3, 3] with target 6? Does your code handle it correctly, and why?
- QHow would you modify this solution if the problem asked you to return all pairs that sum to the target, not just the first one found?
Frequently Asked Questions
Why use a HashMap for Two Sum instead of sorting the array?
Sorting + two-pointer is another valid O(n log n) approach, but it destroys the original indices — you'd need extra work to recover them. The HashMap approach is O(n) time, preserves indices naturally, and is generally the preferred answer in interviews unless the problem specifically asks for sorted output or forbids extra memory.
What if there are multiple valid pairs that sum to the target?
The classic Two Sum problem guarantees exactly one solution, but if you need all pairs, switch your result storage from a single return to a List of int arrays. Instead of returning immediately when you find a match, add the pair to the list and keep iterating. The overall O(n) complexity still holds.
Does this solution work if the array contains negative numbers or zeros?
Yes, completely. HashMap keys are just integers — they work with any value including negatives and zero. The complement calculation (target - currentNumber) works correctly with all integers. For example, numbers=[-3, 3] with target=0 correctly finds the pair, as shown in Test Case 4 in the code above.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.