Two Sum in Java DSA: From Brute Force to the One-Pass HashMap

Learn Two Sum in Java DSA step by step, from brute force to the one-pass HashMap. Full dry runs, clean code, and complexity comparison for beginners.

1. Introduction

Two Sum in Java is the problem almost everyone starts with. It shows up on day one of most interview prep lists, and for good reason. It teaches a trick you will reuse in dozens of harder problems: trading a bit of memory to save a lot of time.

The task is short. You get an array of numbers and a target. You must find two numbers that add up to that target, and return their positions.

There is one small promise that makes life easier. Each input has exactly one answer, and you cannot use the same element twice. So you never have to worry about ties or missing pairs.

We solve it in three steps, from slow to fast. Brute force checks every pair with two loops. A sort-and-two-pointer version trims the search on a sorted copy. The one-pass HashMap is the version interviewers actually want, and it runs in a single sweep.

Every approach gets a full, step-by-step dry run on the same five numbers. Nothing is skipped, so you can see exactly what each line does and what changes on every step.

2. Understanding the Problem

Let us pin down the rules before we touch any code.

• You get an array of integers, like [3, 2, 6, 7, 11].
• You also get a target number, say 10.
• Return the two positions whose values add up to the target.
• Exactly one valid pair exists, and the same slot cannot be used twice.

For our array the answer is [0, 3], because nums[0] is 3 and nums[3] is 7, and 3 + 7 makes 10. Notice we return indices, not the values. That detail matters later, and it decides which approach truly wins.

3. Concepts You Need Here

3.1 The Complement Idea

For any number x, the partner we need is target minus x. We call that the complement. If x is 3 and the target is 10, then we are hunting for a 7 somewhere else in the array.

This one idea powers the fast solution. Instead of testing pairs blindly, we look up the exact partner we want.

3.2 A HashMap for Instant Lookups

A HashMap lets us ask “have I seen this value already?” in roughly constant time. We store each number as we pass it, with its index as the value. Later, a single lookup tells us if the complement went by earlier.

3.3 Two Pointers on a Sorted Array

If we sort the numbers first, we can walk two pointers inward from both ends. One pointer lower starts on the left, the other pointer higher starts on the right. The sort tells each pointer which way to move.

• Sum too small? Move lower right for a bigger value.
• Sum too big? Move higher left for a smaller value.
• Sum just right? We found the pair.

4. Approach 1: Brute Force

Try every possible pair of numbers. Keep the pair that hits the target. It is slow, but it proves you understand the goal.

4.1 Pseudocode

for i from 0 to n-1:          // first number
    for j from i+1 to n-1:    // second number
        if nums[i] + nums[j] == target:
            return [i, j]
return []                     // no pair (won't happen here)

4.2 Pseudocode Explained

• The outer loop picks the first number at index i.
• The inner loop picks a second number after it, so no pair repeats.
• When the two add up to the target, return both positions right away.

4.3 Java Code

import java.util.*;
 
public class TwoSumBrute {
 
    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; 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 pair found
    }
 
    public static void main(String[] args) {
        int[] nums = { 3, 2, 6, 7, 11 };
        System.out.println(Arrays.toString(twoSum(nums, 10))); // [0, 3]
    }
}

4.4 Java Code Explained

• Line 6 runs the outer loop over the first number i.
• Then line 7 loops j over every number that sits after i.
• Line 8 checks whether the two chosen numbers reach the target.
• On a hit, line 9 returns both indices and the method stops.

4.5 Dry Run of the Brute Force

Array: [3, 2, 6, 7, 11], target 10. The two loops try pairs in order until one works. We trace every attempt, so nothing is hidden.

4.6 Reading the Dry Run

Let us walk the trace one step at a time and watch the two loops move.

The outer loop fixes i on the first number, which is 3. Now j sweeps every number to its right, looking for a partner that makes 10. So j is really hunting for a 7.

• Step 1: i is 3 and j is 2. Their sum is 5, well below 10. No match, so j slides one place right.
• Step 2: i is still 3, j is now 6. The sum climbs to 9, closer but not 10. Again no match, so j moves right once more.
• Step 3: i is 3, j reaches 7. Now 3 + 7 equals 10, a real hit. We return [0, 3] and the method ends on the spot.

Notice the method never needed the outer loop to advance past index 0. The very first number found its partner. On a bigger or unlucky array, though, i would keep marching and j would restart each time, which is exactly why this approach gets slow.

4.7 Time and Space Cost

• Time is O(n squared), because of the two nested loops over the array.
• Space is O(1), since we only use a couple of loop counters.

Three checks for five numbers feels fine. For a few thousand numbers the pair count explodes, which is why we sharpen it next.

5. Approach 2: Sort and Two Pointers

Sort a copy of the array, then send two pointers inward from both ends. The sort gives each pointer a reliable direction, so we skip huge chunks of pairs at once.

One honest catch: sorting scrambles the original positions. So this version naturally finds the two values, not their original indices. We will see that clearly in the dry run.

5.1 Pseudocode

sort a copy of nums
lower = 0
higher = n - 1
while lower < higher:
    sum = arr[lower] + arr[higher]
    if sum == target:  return the two values
    else if sum < target:  lower = lower + 1
    else:  higher = higher - 1

5.2 Pseudocode Explained

• lower starts on the smallest value, higher on the largest.
• A small sum means we need more, so lower steps right toward bigger numbers.
• A big sum means we overshot, so higher steps left toward smaller numbers.
• When the sum equals the target, the two pointed values are the answer.

5.3 Java Code

import java.util.*;
 
public class TwoSumTwoPointer {
 
    public static int[] twoSum(int[] nums, int target) {
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int lower = 0, higher = arr.length - 1;
        while (lower < higher) {
            int sum = arr[lower] + arr[higher];
            if (sum == target) {
                return new int[] { arr[lower], arr[higher] };
            } else if (sum < target) {
                lower++;
            } else {
                higher--;
            }
        }
        return new int[] {};
    }
 
    public static void main(String[] args) {
        int[] nums = { 3, 2, 6, 7, 11 };
        System.out.println(Arrays.toString(twoSum(nums, 10))); // [3, 7]
    }
}

5.4 Java Code Explained

• Line 6 clones the array so the original order stays untouched.
• Then line 7 sorts that copy from smallest to largest.
• Line 8 places lower at the front and higher at the back.
• Lines 11 to 17 compare the sum with the target and slide one pointer inward.

5.5 Dry Run of the Two-Pointer Sweep

Sorted copy: [2, 3, 6, 7, 11], target 10. We trace every while step, including the moves that find nothing, so the pointer motion is fully visible.

Legend: lower is the left pointer moving right, higher is the right pointer moving left, and sum adds the two pointed values.

5.6 Reading the Dry Run

Let us follow the two pointers step by step and see why each one moves the way it does.

Before we start, lower sits at index 0 on the value 2, and higher sits at index 4 on the value 11. We want the two pointed values to add up to 10.

• Step 1: 2 + 11 gives 13, which overshoots 10. The array is sorted, so the only way to shrink the sum is a smaller value on the right. We move higher left, from index 4 to index 3.
• Step 2: Now 2 + 7 gives 9, just under 10. To grow the sum we need a bigger value on the left. So we move lower right, from index 0 to index 1.
• Step 3: Here 3 + 7 makes exactly 10. That is our pair, so we return the values 3 and 7.

Three steps settled it, and the pointers never crossed back over ground they already covered. That is the whole charm of two pointers: every move rules out a batch of pairs, not just one.

But look closely at what we returned: the values 3 and 7, not their spots in the original array. Two Sum wants indices, and sorting threw those away. That gap is exactly why the next approach wins.

5.7 Time and Space Cost

• Time is O(n log n), dominated by the sort; the pointer sweep itself is only O(n).
• Space is O(n) for the sorted copy of the array.

Faster than brute force on large inputs. Still, the sort adds cost and the index problem lingers, so we go leaner one more time.

6. Approach 3: One-Pass HashMap

This is the answer interviewers hope to see. We walk the array once. For each number we ask the map whether its complement already went by. If yes, we are done; if no, we drop the current number in and keep going.

6.1 Pseudocode

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

6.2 Pseudocode Explained

• seen remembers each value we pass, along with where we saw it.
• need is the complement, the partner that would complete the target.
• If need is already in the map, its stored index plus the current index is the answer.
• Otherwise we record the current number and move on.

6.3 Java Code

import java.util.*;
 
public class TwoSumHashMap {
 
    public static int[] twoSum(int[] nums, int target) {
        Map<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 = { 3, 2, 6, 7, 11 };
        System.out.println(Arrays.toString(twoSum(nums, 10))); // [0, 3]
    }
}

6.4 Java Code Explained

• Line 6 creates the map from a value to the index where we saw it.
• Then line 8 computes need, the exact complement for the current number.
• Line 9 checks whether that complement is already sitting in the map.
• On a hit, line 10 returns the stored index and the current one; otherwise line 12 saves the current number.

6.5 Dry Run of the HashMap Approach

Array: [3, 2, 6, 7, 11], target 10. We trace every index, showing the complement, the map before the check, and what changes after. The map starts empty.

6.6 Reading the Dry Run

Let us go index by index and watch the map decide each step.

• i = 0, value 3: we need 7. The map is empty, so no match. We store 3 with its index 0, and the map becomes { 3:0 }.
• i = 1, value 2: we need 8. The map holds only { 3:0 }, so no 8 is there. We store 2 at index 1, giving { 3:0, 2:1 }.
• i = 2, value 6: we need 4. The map holds { 3:0, 2:1 }, and 4 is missing. So we store 6 at index 2, and the map grows to { 3:0, 2:1, 6:2 }.
• i = 3, value 7: we need 3. This time the map already has 3, saved back at index 0. Match. We return [0, 3] straight away.

One timing rule ties it together. We check for the complement first, then store the current number. That order is what stops a number from wrongly matching itself, and it is why the 3 from index 0 was sitting ready when its partner 7 arrived.

Also notice the payoff over brute force. We touched each number once and never looped back. The map did the searching for us, so five numbers meant four quick checks instead of a growing pile of pairs.

7. The Dry Run on Paper

Tables are precise, but a sketch often lands faster. Here is the same one-pass HashMap trace drawn by hand.

• Each box shows the number being read and the complement it is hunting for.
• A green mark lands on the step where the complement is finally found.
• At the bottom, the finished answer reads [0, 3].

8. Comparing the Three Approaches

All three can find a valid pair. They just pay different prices, and one of them also solves the index problem cleanly.

The HashMap wins on two fronts. It runs in a single pass, and it returns the exact indices the problem asks for. The two-pointer method is clever, but for Two Sum specifically it fights the index requirement.

In an interview, start with brute force, point out the wasted second loop, then jump to the HashMap and explain the complement trick. That climb is the story interviewers want to hear.

9. Common Mistakes and Edge Cases

A few small traps catch beginners on Two Sum. Keep them in mind.

• Returning values instead of indices. The problem wants positions, so a sorted two-pointer answer needs extra bookkeeping.
• Storing a number in the map before checking its complement, which lets an element pair with itself.
• Looping j from 0 instead of i+1 in brute force, which double-counts and reuses the same slot.
• Assuming the array is sorted. The input order is arbitrary unless the problem says otherwise.
• Forgetting the guarantee of exactly one answer, then writing extra handling the problem never needs.

Run a tiny case like [3, 3] with target 6 through your code. It quickly reveals a self-pairing bug if you stored before checking.

10. Interview Questions

11. Conclusion

Two Sum in Java looks tiny, yet it hides a habit you will use everywhere. Brute force grinds through pairs. The HashMap flips the problem around and asks a smarter question: have I already seen the partner I need?

Our five-number trace made the payoff clear. The brute force checked pairs until one worked. The HashMap swept once, remembered as it went, and found the answer the instant the complement showed up.

So take the pattern, not just the answer. When you catch yourself testing every pair, ask whether a map of what you have seen could answer the question in one look. That instinct will carry you through many array problems further down the list.

12. Further Reading

• LeetCode Two Sum problem — practice the original problem and submit your own solution.
• Oracle Java HashMap documentation — the official reference for the map used in the fast approach.
• Start of this series: javahandson.com DSA Series — the full ordered list of problems, worked from easy to hard.
• Next in this series: Best Time to Buy and Sell Stock in Java — track a running minimum to find the biggest profit in one pass.

javahandson.com | DSA Series | Arrays & Strings