3Sum in Java DSA: From the Triple Loop to the Two-Pointer Sweep

Learn 3Sum in Java DSA step by step, from a simple brute-force triple loop to the clean sort-and-two-pointer solution, with dry runs and beginner-friendly explanations.

1. Introduction

3Sum in Java is the problem where two-pointer thinking really starts to pay off. You have already met the two-pointer idea in easier problems. Here you get to use it on something with a bit more bite.

The task sounds short. You get an array of numbers. You must find every group of three numbers that adds up to zero.

One catch makes people sweat. You cannot repeat the same triplet twice. So [-1, 0, 1] should show up once, even if the array could form it in more than one way.

We build the answer in three steps, same as always. Brute force checks every possible trio with three loops. A cleaner version sorts first and uses a hash set for the third number. The final one sorts and then walks two pointers inward, which is the answer interviewers want to see.

Every approach comes with a full, step-by-step dry run on the same six numbers. Nothing is skipped, so you can follow exactly what each line does and what changes at every step.

2. Understanding the Problem

Let us pin down the rules before touching code.

• You get an array of integers, like [-1, 0, 1, 2, -1, -4].
• Find all triplets that add up to 0.
• The three numbers must sit at three different positions.
• No triplet may repeat. Each distinct trio appears once.

For our array the answer is [[-1, -1, 2], [-1, 0, 1]]. The array has two copies of -1, so a careless solution prints the same triplet twice. Handling that is the real challenge.

3. Concepts You Need Here

3.1 Sorting First

We sort the array before we start, so [-1, 0, 1, 2, -1, -4] becomes [-4, -1, -1, 0, 1, 2]. Sorting helps in two ways.

• Equal numbers end up next to each other, so duplicates are easy to skip.
• We always know which way values grow, so two pointers can steer correctly.

3.2 The Two-Pointer Idea

Fix one number, then chase the other two with two pointers. One pointer lower starts just after the fixed number. The other pointer higher starts at the far right end.

• Sum too small? Move lower right for a bigger value.
• Sum too big? Move higher left for a smaller value.
• Sum is zero? Save the triplet, then move both inward.

Once you fix the first number, you only need two more that sum to its negative. So 3Sum is really “pick one number, then solve 2Sum on the rest.”

4. Approach 1: Brute Force

Try every possible group of three numbers. Keep the ones that sum to zero. It is slow, but it proves you understand the goal.

4.1 Pseudocode

sort nums
result = empty set of triplets
 
for a from 0 to n-1:            // first number
    for b from a+1 to n-1:     // second number
        for c from b+1 to n-1: // third number
            if nums[a] + nums[b] + nums[c] == 0:
                add sorted [nums[a], nums[b], nums[c]] to result
 
return result as a list

4.2 Pseudocode Explained

• Sort first so each triplet is written in one fixed order.
• Three loops pick three different slots: a, then b after a, then c after b.
• Starting b after a and c after b means we never reuse a slot or repeat a trio.
• If the three add to zero, save them in a set.
• A set refuses copies, so a repeated triplet is kept only once.

4.3 Java Code

import java.util.*;
 
public class ThreeSumBrute {
 
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> found = new HashSet<>();
 
        for (int a = 0; a < nums.length - 2; a++) {
            for (int b = a + 1; b < nums.length - 1; b++) {
                for (int c = b + 1; c < nums.length; c++) {
                    if (nums[a] + nums[b] + nums[c] == 0) {
                        found.add(Arrays.asList(nums[a], nums[b], nums[c]));
                    }
                }
            }
        }
        return new ArrayList<>(found);
    }
 
    public static void main(String[] args) {
        int[] nums = { -1, 0, 1, 2, -1, -4 };
        System.out.println(threeSum(nums)); // [[-1, -1, 2], [-1, 0, 1]]
    }
}

4.4 Java Code Explained

• Line 6 sorts the array.
• Then line 7 makes a HashSet, our automatic duplicate blocker.
• Lines 9 to 11 are the three loops for a, b and c.
• Inside them, line 12 adds the three numbers and checks for zero.
• On a match, line 13 saves the triplet; the set drops any copy.
• Finally, line 19 returns the set as a list.

4.5 Dry Run of the Brute Force

Sorted array: [-4, -1, -1, 0, 1, 2]. The three loops try every trio in order. We trace all 20 of them, so nothing is hidden. Watch the set on the right.

4.6 Reading the Dry Run

Let us walk the whole trace, group by group, and see what the loops are doing.

Steps 1 to 10: a is fixed at -4.

The outer loop parks a on the -4 at index 0. Now b and c sweep the rest of the array looking for two numbers that add up to 4, because -4 needs +4 to reach zero.

• Steps 1 to 4: b sits on the first -1, and c walks 0, 1, 2. The sums are -5, -4, -3, all far below zero.
• Steps 5 to 7: b moves to the second -1, and c walks again. Same story, sums stay negative.
• Steps 8 to 10: b moves onto 0, then 1, and c finishes the sweep. The biggest sum here is -1, still short of zero.

The two largest numbers left are 1 and 2, which only add to 3, and 3 is less than 4. So -4 can never find its partners, and the set stays empty.

Steps 11 to 16: a is fixed at the first -1 (index 1).

Now a is -1, so b and c need to add up to 1. This is where the answers live.

• Steps 11 and 12: b on the second -1, c on 0 then 1. Sums are -2 and -1, still too low.
• Step 13: b is on the second -1, c reaches 2. Now -1 + -1 + 2 = 0. First triplet found, so the set becomes { [-1,-1,2] }.
• Step 14: b moves to 0, c to 1. That gives -1 + 0 + 1 = 0. Second triplet found, so the set becomes { [-1,-1,2], [-1,0,1] }.
• Steps 15 and 16: c keeps moving, sums climb to 1 then 2, so nothing is added.

Notice the pattern: once the sum passes zero, larger c values only make it bigger. The brute force cannot use that hint, so it checks them anyway.

Steps 17 to 20: a is fixed at the second -1 (index 2), then 0.

This group holds the one moment that matters most for correctness.

• Step 17: a is now the second -1, b is 0, c is 1. The sum is -1 + 0 + 1 = 0, a real zero. But the triplet [-1, 0, 1] is already in the set from step 14, so the set quietly ignores this copy.
• Steps 18 and 19: c moves on, sums become 1 and 2, no change.
• Step 20: a lands on 0, and the only trio left is 0, 1, 2, which sums to 3. Nothing added.

Step 17 is the whole reason we sort and use a set. Both copies of -1 can build [-1, 0, 1], so without the set we would print it twice. Twenty trios were tested in all, yet only two unique triplets survived.

4.7 Time and Space Cost

• Time is O(n³), because of the three stacked loops.
• Space is O(n) for the set, apart from the answer we must return.

Twenty trios for six numbers is fine. For a few thousand it crawls, which is why we improve it next.

5. Approach 2: Sort and Hash the Third Number

Drop the third loop. Fix the first number, walk the rest, and let a hash set remember what we have already seen. For each value we ask the set whether the partner we need has already gone by.

5.1 Pseudocode

sort nums
result = empty set of triplets
 
for i from 0 to n-3:
    seen = empty hash set
    for j from i+1 to n-1:
        need = -(nums[i] + nums[j])   // partner we want
        if need is in seen:
            add sorted [nums[i], need, nums[j]] to result
        add nums[j] to seen
 
return result as a list

5.2 Pseudocode Explained

• The outer loop fixes the first number, nums[i].
• seen is a fresh notebook, emptied for every new i.
• need is the third number that would make the sum zero.
• If need is already in the notebook, the three numbers add to zero, so save them.
• Add nums[j] to seen after the check, so a number never pairs with itself.

5.3 Java Code

import java.util.*;
 
public class ThreeSumHashSet {
 
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> result = new HashSet<>();
 
        for (int i = 0; i < nums.length - 2; i++) {
            Set<Integer> seen = new HashSet<>();
            for (int j = i + 1; j < nums.length; j++) {
                int need = -(nums[i] + nums[j]);
                if (seen.contains(need)) {
                    result.add(Arrays.asList(nums[i], need, nums[j]));
                }
                seen.add(nums[j]);
            }
        }
        return new ArrayList<>(result);
    }
 
    public static void main(String[] args) {
        int[] nums = { -1, 0, 1, 2, -1, -4 };
        System.out.println(threeSum(nums)); // [[-1, -1, 2], [-1, 0, 1]]
    }
}

5.4 Java Code Explained

• Line 6 sorts, line 7 makes the result set that keeps triplets unique.
• The outer loop on line 9 fixes the first number; line 10 makes a fresh seen set.
• Then line 12 computes need, the exact partner for a zero sum.
• Lines 13 to 15 save the triplet when need was already seen.
• Line 16 records nums[j], but only after the check.

5.5 Dry Run of the HashSet Approach

Sorted array: [-4, -1, -1, 0, 1, 2]. We trace every i pass and every j step, so nothing is skipped. seen resets to empty at the top of each pass.

Pass i = 0, nums[i] = -4, seen = { }:

Nothing matched with -4 fixed, because no needed partner was ever in the notebook first.

Pass i = 1, nums[i] = -1, seen = { }:

This pass finds both triplets. At j=4 we needed 0, which was already noted, so [-1, 0, 1]. At j=5 we needed -1, also noted, so [-1, -1, 2].

Pass i = 2, nums[i] = -1, seen = { }:

At j=4 the trio [-1, 0, 1] forms again, this time from the second -1. The outer result set already holds it, so it is ignored. This is the duplicate guard doing its job.

Pass i = 3, nums[i] = 0, seen = { }:

No partner is ever found here, so this pass adds nothing. Passes for i = 4 and beyond have too few numbers left to form a triplet.

5.6 Reading the Dry Run

Let us go pass by pass and watch how the notebook decides each match.

Pass i=0, first number -4.

With -4 fixed, every partner we need is a large positive number. At j=1 we need 5, at j=3 we need 4, and so on. But the notebook only ever fills with -1, 0, 1, 2, so the number we need is never in it.

• Each step writes nums[j] into seen, but no step ever asks for a value that is already there.
• So this whole pass finds nothing, which matches the brute force result for -4.

Pass i=1, first number -1.

Now seen starts empty again, and we hunt for two numbers that add up to 1.

• j=2 (-1): we need 2. The notebook is empty, so no match. We write -1 into seen.
• j=3 (0): we need 1. The notebook holds only -1, so no match. We write 0 into seen.
• j=4 (1): we need 0. The notebook now holds { -1, 0 }, and 0 is there. Match. We save [-1, 0, 1].
• j=5 (2): we need -1. The notebook holds { -1, 0, 1 }, and -1 is there. Match. We save [-1, -1, 2].

Both triplets fall out of this single pass. Each match happened because the partner had already been written down on an earlier step of the same pass.

Pass i=2, first number -1 again.

This is the duplicate pass, and it shows why we keep an outer result set.

• j=3 (0): we need 1, notebook empty, no match. We write 0.
• j=4 (1): we need 0, and 0 is in the notebook. This forms [-1, 0, 1] all over again, this time using the second -1.
• But the result set already holds [-1, 0, 1], so the copy is ignored.
• j=5 (2): we need -1, notebook holds { 0, 1 }, no match.

So this pass rediscovers a triplet we already had. The result set is what stops it from appearing twice.

Pass i=3, first number 0.

• At j=4 (1): we need -1, notebook empty, no match.
• Then j=5 (2): we need -2, notebook holds { 1 }, no match.

Nothing matches, and passes for later i values have fewer than two numbers left, so they add nothing either.

One timing rule ties it all together. We write nums[j] into the notebook only after we check it. That is why at j=4 the 0 recorded back at j=3 is ready and waiting, and why a number can never wrongly match itself.

5.7 Time and Space Cost

• Time is O(n²), because two loops replace the old three.
• Space is O(n) for the seen set and the result set.

A big jump over brute force. But it still carries a notebook each pass, and interviewers usually want the leaner version next.

6. Approach 3: Sort and Two-Pointer Sweep

On a sorted array we do not need a notebook. Fix the first number, then send two pointers inward from both ends. The sort tells the pointers which way to move. This is the answer interviewers hope to see.

6.1 Pseudocode

sort nums
result = empty list
 
for i from 0 to n-3:
    if i > 0 and nums[i] == nums[i-1]:
        continue                    // skip duplicate first number
    lower = i + 1
    higher = n - 1
    while lower < higher:
        sum = nums[i] + nums[lower] + nums[higher]
        if sum < 0:  lower = lower + 1
        else if sum > 0:  higher = higher - 1
        else:
            add [nums[i], nums[lower], nums[higher]] to result
            skip lower right past equal values
            skip higher left past equal values
            lower = lower + 1
            higher = higher - 1
 
return result

6.2 Pseudocode Explained

• The outer loop fixes the first number, nums[i].
• If nums[i] equals the previous number, skip the pass to avoid repeat triplets.
• lower starts after i, higher starts at the end; they close in while lower < higher.
• sum too small, move lower right; sum too big, move higher left.
• sum zero, save the triplet, skip equal neighbours, then step both inward.

6.3 Java Code

import java.util.*;
 
public class ThreeSumTwoPointer {
 
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
 
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // skip duplicate first number
            }
            int lower = i + 1, higher = nums.length - 1;
            while (lower < higher) {
                int sum = nums[i] + nums[lower] + nums[higher];
                if (sum < 0) {
                    lower++;
                } else if (sum > 0) {
                    higher--;
                } else {
                    result.add(Arrays.asList(nums[i], nums[lower], nums[higher]));
                    while (lower < higher && nums[lower] == nums[lower + 1]) lower++;
                    while (lower < higher && nums[higher] == nums[higher - 1]) higher--;
                    lower++;
                    higher--;
                }
            }
        }
        return result;
    }
 
    public static void main(String[] args) {
        int[] nums = { -1, 0, 1, 2, -1, -4 };
        System.out.println(threeSum(nums)); // [[-1, -1, 2], [-1, 0, 1]]
    }
}

6.4 Java Code Explained

• Line 6 sorts the array.
• Lines 10 to 12 skip a first number equal to the previous one.
• Line 13 sets lower after i and higher at the end.
• Line 15 adds the three numbers into sum.
• Lines 16 to 19 move lower right or higher left based on the sum.
• Lines 20 to 26 save a match, skip equal neighbours, then step both pointers in.

6.5 Dry Run of the Two-Pointer Sweep

Sorted array: [-4, -1, -1, 0, 1, 2]. We trace every i pass and every while step, including the passes that find nothing and the one we skip.

Pass i = 0, nums[i] = -4, lower = 1, higher = 5:

The sum stayed negative all the way, so lower kept sliding right until it met higher. No triplet with -4.

Pass i = 1, nums[i] = -1, lower = 2, higher = 5:

Both triplets come from this single pass. Each time the sum hit 0 we saved the trio and closed both pointers inward, until they crossed.

Pass i = 2, nums[i] = -1:

nums[2] (-1) equals nums[1] (-1), so the continue skips this whole pass. Without this skip we would rebuild [-1, -1, 2] and [-1, 0, 1] all over again.

Pass i = 3, nums[i] = 0, lower = 4, higher = 5:

The sum was too big, so higher moved left and the pointers met. Nothing found. Later i values have fewer than two numbers left, so the loops stop.

Legend: lower is the left pointer moving right, higher is the right pointer moving left, and sum adds the fixed nums[i] to both pointed values.

6.6 Reading the Dry Run

Let us go pass by pass and watch the two pointers steer.

Pass i=0, first number -4.

lower starts at index 1 and higher at index 5. We need the two pointed numbers to add up to 4.

• lower=1, higher=5: sum is -1 + 2 + (-4) = -3. Too small, so lower steps right for a bigger value.
• lower=2, higher=5: sum is -3 again. Still too small, lower steps right.
• lower=3, higher=5: sum is -2. Closer, but still below zero, lower steps right.
• lower=4, higher=5: sum is -1. Almost there, but still short, lower steps right.
• Now lower=5 and higher=5, so lower is not less than higher and the pass ends.

The sum never reached zero because -4 is too negative for the numbers on its right. Moving lower right was the correct choice every time, since the sorted array grows in that direction.

Pass i=1, first number -1.

lower starts at index 2 and higher at index 5. Now the two pointers only need to add up to 1, and this pass finds both answers.

• lower=2, higher=5: sum is -1 + -1 + 2 = 0. A match. We save [-1, -1, 2], then move both pointers inward to lower=3, higher=4.
• lower=3, higher=4: sum is -1 + 0 + 1 = 0. Another match. We save [-1, 0, 1], then move both inward to lower=4, higher=3.
• Now lower=4 and higher=3, so lower has passed higher and the pass ends.

Each time the sum hit zero, we grabbed the triplet and closed in from both sides at once. There were no equal neighbours to skip here, so the plain inward step was enough.

Pass i=2, first number -1 again.

Before setting up any pointers, the code checks nums[2] against nums[1]. Both are -1, so the continue skips this entire pass.

• If we did not skip, lower and higher would repeat the exact search from pass i=1.
• That would rebuild [-1, -1, 2] and [-1, 0, 1] a second time.

This single skip is what keeps the plain list free of duplicates, so we never need a set here.

Pass i=3, first number 0.

lower starts at index 4 and higher at index 5.

• lower=4, higher=5: sum is 0 + 1 + 2 = 3. Too big, so higher steps left for a smaller value.
• Now lower=4 and higher=4, so lower is not less than higher and the pass ends.

This time the sum was too large, so we moved higher instead of lower. Nothing matched. Later i values have fewer than two numbers left, so the outer loop stops.

Across all four passes, every step did exactly one of three things: found a match and closed in, nudged lower right for a bigger sum, or nudged higher left for a smaller sum. The pointers only ever move toward each other, so no trio is checked twice and no extra memory is needed.

6.7 Comparing the Three Traces

7. The Dry Run on Paper

Tables are exact, but a sketch often lands faster. Here is the same two-pointer trace drawn by hand.

• A green block marks each moment the sum hits zero and a triplet is saved.
• A gold block marks where the pointers cross and the pass ends.
• At the bottom, the finished answer reads [[-1, -1, 2], [-1, 0, 1]].

8. Comparing the Three Approaches

All three give the same answer. They just pay different prices.

The two faster versions share the same time class. What separates them is memory. A two-pointer sweep carries almost nothing, and its duplicate handling is two small skips.

In an interview, start with brute force, point out the wasted third loop, then tighten it into the two-pointer sweep and explain the two duplicate guards. That climb is the story interviewers want to hear.

9. Common Mistakes and Edge Cases

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

• Forgetting to sort first breaks both the pointer direction and the duplicate skipping.
• Skipping the duplicate guards prints the same triplet more than once.
• Moving only one pointer after a match can miss triplets or loop forever, so step both.
• An array shorter than three numbers, like [0, 1], has no triplets and should return empty.
• An array of all zeros, like [0, 0, 0, 0], should return [[0, 0, 0]] exactly once.

Run those last two cases through your code before you call it done. They catch more bugs than any ordinary input will.

10. Interview Questions

11. Conclusion

3Sum in Java looks scary at first, with its triplets and its no-repeat rule. But once you sort the array, most of the fear melts away.

Our six-number trace showed the payoff clearly. Brute force ground through every trio. The two-pointer sweep fixed one number and let two pointers close in, finding both triplets in a couple of clean steps.

So take the pattern, not just the answer. Sort when order helps you. Fix one number to shrink a hard problem into an easier one. Then let two pointers do the walking.

That habit turns a slow cube of work into something fast and tidy. It will do the same for many array problems waiting further down the list.

12. Further Reading

• LeetCode 3Sum problem — practice the original problem and submit your own solution.
• Oracle Java Arrays documentation — the official reference for Arrays.sort and other helpers used here.
• Previous in this series: Reverse String in Java — flip a character array in place with two pointers.
• Next in this series: Container With Most Water in Java — use two pointers to trap the largest area between lines.