Two Sum in Java Explained: Brute Force and the HashMap Trick

Learn the Two Sum in Java problem step by step. See the brute-force solution, the fast HashMap approach, a full dry run, and clear, beginner-friendly code.

1. Introduction

The Two Sum problem in Java is usually the first question people meet when they start with arrays. It looks tiny. Yet it teaches a habit that shows up in dozens of harder problems later. So it is worth slowing down and really getting it.

Here is the task in plain words. You get an array of numbers and one target value. You must find two numbers that add up to the target. Then you return their positions in the array.

In this guide, we start with the slow but obvious way. After that, we speed it up with a clever trick using a HashMap. We also dry-run the code by hand, so you can see exactly what happens on each step. By the end, this problem will feel simple.

2. Understanding the Problem

Let us pin down the rules first. A clear problem statement saves you from silly bugs later.

• You are given an array of integers, for example, [2, 7, 11, 15].
• There is also a target, for example, 9.
• Your job is to return the two indexes whose values add up to the target.
• Each input has exactly one answer, and you cannot use the same element twice.

So, for the array above with a target of 9, the answer is [0, 1]. Why? Because nums[0] is 2 and nums[1] is 7, and 2 plus 7 equals 9. Notice that we return positions, not the numbers themselves. Beginners mix this up all the time.

3. Approach 1: Brute Force

The first idea most people have is simple. Check every possible pair of numbers. If any pair adds up to the target, return those two positions.

3.1 Pseudocode

for i from 0 to n-1:
    for j from i+1 to n-1:
        if nums[i] + nums[j] == target:
            return [i, j]
return []   // no pair found

The outer loop picks the first number. The inner loop picks a later number to pair with it. We start j at i plus 1, so we never pair a number with itself. Also, this avoids checking the same pair twice.

3.2 Java Code

public class TwoSumBrute {
    public static 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[] {}; // no answer
    }
 
    public static void main(String[] args) {
        int[] nums = { 2, 7, 11, 15 };
        int[] ans = twoSum(nums, 9);
        System.out.println(ans[0] + ", " + ans[1]); // 0, 1
    }
}

3.3 Why This Works, Step by Step

Let us walk through the code slowly. Each line has a clear job.

• The outer loop variable i points to the first number in a pair.
• The inner loop variable j points to a number after i. This way we test i with every later number.
• Inside, we add nums[i] and nums[j]. Then we compare that sum with the target.
• If they match, we return both indexes at once as a small array.
• If no pair matches after all loops, we return an empty array.

This code is easy to read and hard to get wrong. That is its main strength. The problem is speed, which we will fix next.

3.4 Time and Space Cost

The brute force checks roughly every pair. For an array of size n, that is about n times n over two comparisons. So the time is O(n²). The space stays O(1) because we only use a few variables. For small arrays, this is fine. For large ones, it gets slow quickly.

4. Approach 2: The HashMap Trick

Now for the smart version. The key idea is to remember the numbers we have already seen. As we walk the array once, we ask a simple question at each step. Have I already seen the number I still need?

For each number, the number we need is the target minus the current number. If that needed number sits in our memory, we are done. If not, we store the current number and move on.

4.1 Pseudocode

seen = empty map   // value -> index
for i from 0 to n-1:
    need = target - nums[i]
    if need is in seen:
        return [seen[need], i]
    seen[nums[i]] = i
return []

4.2 Java Code

import java.util.HashMap;
 
public class TwoSumHashMap {
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seen.containsKey(need)) {
                return new int[] { seen.get(need), i };
            }
            seen.put(nums[i], i);
        }
        return new int[] {};
    }
 
    public static void main(String[] args) {
        int[] nums = { 2, 7, 11, 15 };
        int[] ans = twoSum(nums, 9);
        System.out.println(ans[0] + ", " + ans[1]); // 0, 1
    }
}

4.3 Reading the Code Line by Line

This version does more thinking, so let us break it down gently.

• We create a HashMap called seen. It maps a value to the index where we found it.
• We loop once through the array. There is no inner loop here, which is the whole point.
• For each number, we compute the need, the partner value that would complete the target.
• Next, we check if the need already lives in the map. If yes, we return its stored index and the current one.
• Otherwise, we save the current number and its index, then continue.

Because a HashMap lookup is fast on average, each check takes constant time. So one pass through the array is enough. That single change is what makes this approach shine.

5. Dry Run of the HashMap Approach

Watching the code run by hand makes it stick. Let us use nums = [2, 7, 11, 15] and target = 9. We track the map as it changes.

Look at step two closely. We reach the number 7. Its partner is 2, and 2 is already sitting in the map from step one. So we return the stored index 0 with the current index 1. That gives us [0, 1], and we never even touch 11 or 15.

5.1 The Same Dry Run on Paper

The sketch above shows the same trace. The array sits on top, the memory map sits below, and the arrows show how 7 finds its partner 2. Many people find this picture easier than the table, so use whichever one clicks for you.

6. Brute Force vs HashMap

Both approaches return the correct answer. They just pay different prices. Here is the plain comparison.

• Brute force runs in O(n²) time and O(1) space. It is simple but slow on big inputs.
• HashMap runs in O(n) time and O(n) space. It is faster because it trades a little memory for a lot of speed.

In an interview, start by mentioning the brute force. It shows you understand the problem. Then improve it with the HashMap to show you can optimize. That path from slow to fast is exactly what interviewers want to see.

7. Common Mistakes and Edge Cases

A few small traps catch beginners on this problem. Keep these in mind.

• Do not pair a number with itself. Storing the current number after the check cleanly avoids this.
• Return indexes, not values. This is the most common slip in interviews.
• Negative numbers and zeros work fine. The math does not care about the sign.
• Duplicate values are handled correctly because we check for them before storing each number.

8. Conclusion

The Two Sum problem in Java looks like a warm-up, and it is. But the HashMap trick inside it is a real skill. You will reuse that same remember-as-you-go idea in many tougher array and string problems.

So take the lesson, not just the answer. Brute force first to be safe. Then reach for a HashMap when you need speed. Once that pattern feels natural, a whole family of problems opens up for you.

9. Interview Questions on Two Sum

10. What’s Next

You now have Two Sum in your toolkit, so let us keep the momentum going. The next problem in this series is a classic that builds the same one-pass habit you just learned.

• Next up: Best Time to Buy and Sell Stock. You track the lowest price so far and the best profit in one pass.

11. Further Reading

• LeetCode Two Sum problem — practice the original problem and test your solution.
• Oracle Java HashMap documentation — the official reference for the class used here.