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 dry run. We trace the same six numbers through the best version, so you can watch the pointers close in and the triplets fall out.

2. Understanding the Problem

Let us pin down the rules before touching code. A clear picture now saves you from messy bugs later.

• You get an array of integers, for example [-1, 0, 1, 2, -1, -4].
• You must find all triplets nums[a], nums[b], nums[c] that add up to 0.
• The three numbers must sit at three different positions in the array.
• No triplet may repeat. Each distinct trio appears once in your answer.
• You return a list of these triplets. The order of the triplets does not matter.

For our array the answer is [[-1, -1, 2], [-1, 0, 1]]. Two trios, both summing to zero, and neither one repeated.

Notice the trap early. The array has two copies of -1, so a lazy solution could easily print the same triplet twice. Handling those duplicates cleanly is half the challenge.

2.1 Why Duplicates Are the Hard Part

The math here is easy. Pick three numbers, check if they sum to zero. A child could do it by hand for six numbers.

The pain is the no-repeat rule. Our array holds -1 twice, so the same-looking triplet can form from different slots.

• The trio -1, 0, 1 can use either copy of -1 in the array.
• Both give the exact same result [-1, 0, 1], so we want only one of them.
• A good solution has to spot this and quietly skip the copy.

Every approach below has to answer one question: how do I avoid printing a triplet I already have? That single worry shapes all three solutions.

2.2 Why This Example Array

Our six numbers were picked to be a little annoying, on purpose. That keeps the trace honest.

• There is a repeated -1, so duplicate handling gets tested right away.
• The numbers are unsorted, so we get to see the sort step do real work.
• There are exactly two valid triplets, so the trace has something to find, but stays short.

A tidy input like [-1, 0, 1] would hide all of this. A messy one shows you what the pointers really do.

3. Concepts You Need Here

Three small ideas carry this whole problem. Each one shows up again in later array questions, so it is worth learning them well.

3.1 Sorting First

Sorting means we arrange the numbers from smallest to largest before we start. Our array becomes [-4, -1, -1, 0, 1, 2].

Why bother? Two big reasons, and both make the rest of the code easier.

• Once sorted, equal numbers sit next to each other, so duplicates are trivial to skip.
• A sorted array lets us move two pointers with confidence, because we know which way values grow.

Sorting costs a bit of time up front. That cost is small next to the mess it saves us later.

3.2 The Two-Pointer Idea

This is the trick that makes 3Sum click. We fix one number, then chase the other two with two pointers.

One pointer, called lo, starts just after the fixed number. The other, called hi, starts at the far right end.

• When the three numbers add up to too little, we need a bigger value, so lo steps right.
• When they add up to too much, we need a smaller value, so hi steps left.
• And when they hit zero exactly, we save the triplet and move both pointers inward.

Think of two people walking toward each other across a sorted shelf. One nudges right for more, the other nudges left for less, until they meet in the middle.

3.3 Turning 3Sum Into 2Sum

Here is the mental shortcut. Once you fix the first number, the rest is just a two-sum problem in disguise.

Say we fix -4. Now we only need two other numbers that add up to 4, because -4 plus 4 is 0. So the target flips to the negative of the fixed number.

• Fix nums[i], then hunt for two numbers that sum to -nums[i].
• That smaller hunt is exactly what the two pointers handle.
• Do this for every choice of the first number, and you cover every triplet.

So 3Sum is really “pick one number, then solve 2Sum on the rest.” That framing makes the code much less scary.

4. Approach 1: Brute Force

The first idea most people reach for is honest and blunt. Try every possible group of three numbers. Check each one to see if it sums to zero.

It works, but it is slow, and it needs a little extra care to dodge duplicate triplets. Still, it is a great warm-up, because it proves you understand what the answer even is.

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 [nums[a], nums[b], nums[c]] to result
 
return result as a list

4.2 Reading the Pseudocode

Let us walk this one slowly, because the three loops can look intimidating at first. The whole plan is really simple: try every trio, keep the ones that add to zero. Nothing clever, just patience.

Start with the very first line. We sort the array. We do this so that when we build a triplet, its three numbers always come out in increasing order. That small habit is what lets a set catch duplicates for us later, since [-1, -1, 2] will always be written the same way.

Now look at the three nested loops. Picture them as three fingers pointing at three different slots in the array. The outer finger a picks the first number. Its middle neighbour b picks the second. Then the inner finger c picks the third.

• The outer loop moves a from the start toward the end, one slot at a time.
• For each a, the middle loop moves b, and it always starts one slot to the right of a.
• For each b, the inner loop moves c, and it always starts one slot to the right of b.

Why does b start after a, and c start after b? Because we never want to reuse the same slot twice, and we never want to look at the same trio in a different order. Forcing a is left of b is left of c means each group of three positions gets visited exactly once.

Inside the deepest loop sits the only real decision. We add the three chosen numbers together and ask one plain question: does this sum equal zero? If yes, we have found a triplet, so we drop it into result. If no, we do nothing and let the loops roll on to the next trio.

One detail deserves attention. We store answers in a set, not a plain list. A set refuses to hold the same triplet twice. So even though our array has two copies of -1 that could build [-1, 0, 1] in two ways, the set quietly keeps only one. That is our duplicate guard, and it costs us almost no thought.

When all three loops finish, every possible trio has been tried. The set now holds each zero-sum triplet exactly once, and we hand it back as a list. Slow, yes, but you can see at a glance that it cannot miss an answer.

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 Reading the Java Code

Each piece here maps straight to the pseudocode, so let us keep it quick.

• Line 6 sorts the array, so every triplet comes out in increasing order.
• Right after, line 7 makes a HashSet, which is our automatic duplicate blocker.
• Lines 9 to 11 open the three loops that pick the first, second and third numbers.
• Inside them, line 12 adds the three numbers and checks whether they hit zero.
• On a match, line 13 stores the triplet using a fixed order so copies collapse.
• Finally, line 19 pours the set into a list and returns it.

The HashSet is doing the heavy lifting on duplicates here. Because the array is sorted, every equal triplet is written the exact same way, so the set treats them as one.

• Without sorting, [-1, 2, -1] and [-1, -1, 2] would look different to the set.
• With sorting, both become [-1, -1, 2], so the set keeps just one.
• That is a neat trick, but the three loops still make this approach slow.

4.5 Dry Run of the Brute Force

Let us trace the sorted array [-4, -1, -1, 0, 1, 2]. We will only show the trios that actually sum to zero, since the loop tries many that do not.

The loops try many more trios than these four rows. We only listed the ones that matter, so the duplicate story stays clear.

4.6 Reading the Dry Run

A handful of trios summed to zero, but only two are unique. Let us break that down.

• The trio at rows 2 built [-1, -1, 2], our first real triplet.
• The trio at row 3 built [-1, 0, 1], using the first -1 and the 0 and 1.
• Row 4 built [-1, 0, 1] again, this time using the second -1.

Now watch the set do its job on that last row. The triplet [-1, 0, 1] was already inside, so the set simply ignored the copy.

• Both -1 values can pair with 0 and 1 to make the same triplet.
• A plain list would print it twice, which breaks the no-repeat rule.
• The set saves us here, but it hides a lot of wasted work behind the scenes.

4.7 Time and Space Cost

Three nested loops mean we check roughly n times n times n groups. So the time grows fast as the array gets bigger.

• Time is O(n³), because of the three stacked loops over the array.
• Space is O(n) for the set, ignoring the output we must return anyway.

For six numbers this is fine. For a few thousand it crawls, because the cube of a big number is enormous. That speed wall is exactly what we fix next.

5. Approach 2: Sort, Fix One, Hash the Rest

The dry run showed the pain. That third loop is doing far too much work. We can drop it entirely by remembering the numbers we have already seen.

So we keep only two loops. The outer one fixes the first number. The inner one walks through the rest, and for each value it asks a hash set whether the exact partner it needs has already gone by.

This is the same 2Sum-with-a-hashset trick you may know, wrapped inside one outer loop. It trades the third loop for a little extra memory.

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])   // the partner we want
        if need is in seen:
            add sorted triplet [nums[i], need, nums[j]] to result
        add nums[j] to seen
 
return result as a list

5.2 Reading the Pseudocode

This version has one loop fewer than the brute force, so it runs quicker, but it asks you to hold a new idea in your head. That idea is the seen set: a little notebook where we jot down every number we have walked past on this pass. Let us go through it slowly.

First line, we sort again. Same reason as before. Sorting keeps equal numbers together and lets us write each triplet in a fixed order, which makes the outer result set catch duplicates.

Now the outer loop. Its job is to fix the first number of the triplet. Call that fixed number nums[i]. Think of it as saying, “OK, this number is definitely in my trio. Now who are its two partners?”

Right after we fix nums[i], we create a fresh, empty seen set. This is important: it is emptied for every new i. The notebook only remembers numbers from the current pass, not from earlier ones, so old values never leak in and cause wrong matches.

Then the inner loop walks j from just after i to the end. At each stop, it looks at nums[j] and does a tiny bit of arithmetic. We want all three numbers to add to zero. Two of them, nums[i] and nums[j], are already on the table. So the third one, the partner we still need, must be whatever makes the total zero. That value is need, and it equals minus the sum of the two we have.

• If need is already written in our notebook, we have seen it earlier in this pass.
• That earlier number, plus nums[i], plus nums[j], adds to zero, so we have a real triplet.
• We save that triplet, always in sorted order, so copies look identical to the result set.

Here is the part beginners often ask about: when do we write nums[j] into the notebook? Only after we finish checking it. That order matters. It means when we look for need, the notebook holds every number strictly before j, never j itself. So a number can never wrongly pair with itself.

Let us picture it on a tiny slice. Suppose nums[i] is -1, and as j moves we pass a 0. We write 0 in the notebook. Later j lands on 1. We compute need = -(-1 + 1) = 0. We check the notebook, and yes, 0 is there. So -1, 0 and 1 form a zero-sum triplet, and we save it.

When the inner loop ends, we have found every partner pair that works with this fixed nums[i]. The outer loop then slides to the next first number and repeats the whole hunt with a brand new notebook. After all passes, the result set holds each triplet once.

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)) {
                    List<Integer> t = Arrays.asList(nums[i], need, nums[j]);
                    result.add(t);
                }
                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 Reading the Java Code

The shape is close to the pseudocode, so let us focus on the why behind each line.

• Line 6 sorts, so every triplet is stored in one fixed order.
• Next, line 7 makes the outer result set that keeps triplets unique.
• The outer loop on line 9 fixes the first number over i.
• Inside it, line 10 creates a fresh seen set, emptied every time i changes.
• Then line 12 computes need, the exact partner that would complete a zero sum.
• Lines 13 to 16 save the triplet when that partner was already seen.
• Last, line 17 records nums[j] into seen, but only after the check.

Compare this with brute force. We swapped the whole third loop for one hash-set lookup, which is close to instant.

• Brute force asked, let me test every third number one by one.
• This version flips it and asks, is the one number I need already in my notebook?
• That flip drops a full loop, so the running time improves a lot.

5.5 Dry Run of the HashSet Approach

Let us trace the pass where i fixes the first -1, since that pass finds both triplets. The sorted array is [-4, -1, -1, 0, 1, 2], and i sits at index 1.

Two triplets came out of a single pass. The notebook seen did the matching, and the outer result set will keep each one just once.

5.6 Reading the Dry Run

Four inner steps, two triplets found. Let us look closely at how the notebook earned its keep.

• At j is 2, we needed a 2, but the notebook was nearly empty, so no match.
• With j at 3, we needed a 1, which we had not seen yet, so again no match.
• By j is 4, we needed a 0, and 0 was already written down, so we saved [-1, 0, 1].
• Finally at j is 5, we needed a -1, and -1 was in the notebook, so we saved [-1, -1, 2].

Notice the timing rule paying off. Each number was written to seen only after we checked it, so nothing ever matched with itself.

• The 0 was recorded at step 2, ready to be found at step 3.
• The first -1 was recorded at step 1, ready to be found at step 4.
• This tidy ordering is why the notebook trick is safe.

5.7 Time and Space Cost

We dropped a loop, so the time falls hard. The sort adds a small cost that hides under the bigger term.

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

This is already a big jump over brute force. But it still leans on hash sets and extra memory, and interviewers usually want the leaner two-pointer version next.

6. Approach 3: The Sort and Two-Pointer Sweep

The hash-set version is fast, but it carries a notebook for every pass. On a sorted array we do not need that notebook at all.

Instead we fix the first number, then send two pointers inward from both ends of the rest. Because the array is sorted, the pointers always know which way to move. Too small a sum, move the left one right. Too big, move the right one left.

This is the answer interviewers hope to see. It runs in the same O(n²) time as the hash version, but it uses only a couple of index variables, no extra sets per pass.

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
    lo = i + 1
    hi = n - 1
    while lo < hi:
        sum = nums[i] + nums[lo] + nums[hi]
        if sum < 0:  lo = lo + 1
        else if sum > 0:  hi = hi - 1
        else:
            add [nums[i], nums[lo], nums[hi]] to result
            move lo right past any equal values
            move hi left past any equal values
            lo = lo + 1
            hi = hi - 1
 
return result

6.2 Reading the Pseudocode

This is the version worth truly understanding, so we will take it gently and cover every line. The good news: once the array is sorted, the logic is almost mechanical. There is no notebook to track, just two pointers and a running sum.

Line one, we sort. By now you know why. Sorted numbers let the two pointers trust the direction they move, and they let us skip duplicates by simply looking at the neighbour.

Now the outer loop, which fixes the first number nums[i]. Same core idea as before: lock in one number, then hunt for two partners that finish the zero sum. But look at the line right inside the loop, because it is the first duplicate guard.

That guard says: if i is past the start and nums[i] equals the number just before it, skip this whole pass with continue. Why? Because we already ran a full search using that exact value as the first number. Running it again would only rediscover the same triplets. So when we see a repeated first number, we quietly move on.

Next we set up the two pointers. lo starts one slot to the right of i, at the smallest of the remaining numbers. hi starts at the very last slot, the largest. They will now walk toward each other and never cross.

The while loop keeps going as long as lo is still left of hi. Inside it, we add the three numbers, the fixed one plus the two the pointers point at, and store that in sum. Everything now hinges on comparing sum to zero, and there are exactly three cases.

• If sum is less than zero, our total is too small. We need a bigger number, so lo steps one to the right, toward larger values.
• If sum is more than zero, our total is too big. We need a smaller number, so hi steps one to the left, toward smaller values.
• If sum is exactly zero, we found a triplet. We save it, then carefully move both pointers inward.

Why does moving lo right give a bigger sum, and moving hi left give a smaller one? Only because the array is sorted. To lo’s right sit larger numbers. To hi’s left sit smaller numbers. The sort is what makes this steering reliable, and it is the whole reason we sorted in the first place.

Now the trickiest bit, the duplicate skipping after a match. Once we save a triplet, we do not just nudge the pointers by one. We first slide lo rightward past any values equal to the one it just used, and slide hi leftward past any values equal to the one it just used. Only then do we take the final step inward.

• If lo pointed at a -1 and the next slot is also -1, staying there would rebuild the same triplet.
• So we walk lo forward until it lands on a genuinely new value.
• We do the mirror move for hi, walking it back past its equal copies.

Think of the two pointers as two hands closing a book. Every time they meet a matching pair, they clap once, record it, then keep closing until they touch. The equal-value skips just stop them from clapping twice for the same pair.

When lo and hi finally meet, this pass is done. The outer loop moves to the next distinct first number, and the whole closing motion repeats. After every first number has had its turn, result holds every unique triplet, and we return it.

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 lo = i + 1, hi = nums.length - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (sum < 0) {
                    lo++;
                } else if (sum > 0) {
                    hi--;
                } else {
                    result.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
                    while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
                    lo++;
                    hi--;
                }
            }
        }
        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 Reading the Java Code Line by Line

This version does the most thinking in the fewest moving parts, so let us go gently.

• Line 6 sorts the array, which every later step depends on.
• Line 9 opens the outer loop that fixes the first number.
• Lines 10 to 12 skip a first number that matches the previous one, dodging repeats.
• Line 13 sets lo just after i and hi at the far end.
• Line 15 adds the three numbers into sum.
• Lines 16 to 19 nudge lo right for a small sum, or hi left for a big sum.
• Lines 20 to 26 save a match, then skip equal neighbours before stepping both pointers inward.

Two lines quietly carry the whole duplicate story here.

• Line 10 stops us from re-running the search for a repeated first number.
• Lines 22 and 23 stop the pointers from rebuilding a triplet they just made.
• Together they mean the plain ArrayList never holds a repeat, so no set is needed.

6.5 Dry Run of the Two-Pointer Sweep

Now we trace the pass that fixes the first -1, at i index 1. The sorted array is [-4, -1, -1, 0, 1, 2], so lo starts at index 2 and hi at index 5.

Legend: lo is the left pointer moving right, hi is the right pointer moving left, and sum adds the fixed -1 to both pointed values.

6.6 Reading the Dry Run

Two neat steps found both triplets, then the pointers met and stopped. Let us look at each one.

• First, lo at -1 and hi at 2 gave a sum of zero, so we saved [-1, -1, 2].
• After that match both pointers stepped inward, landing on 0 and 1.
• Next, lo at 0 and hi at 1 gave a sum of zero, so we saved [-1, 0, 1].

Then the pointers crossed, and the while loop ended for this pass. There was no wasted checking after that.

• Both matches came from steering the pointers, never from guessing.
• When the sum was zero, we grabbed the triplet and closed in from both sides.
• The moment lo passed hi, the pass was clearly finished.

There is a quiet promise in this loop. Every pass either finds a match and closes in, or nudges one pointer, so the two always march toward each other and never repeat work.

6.7 Comparing the Three Traces

Same array, same two triplets, three very different amounts of work and memory.

The gap grows with size. At six numbers it barely shows. At a few thousand it is the difference between a snappy answer and a long wait.

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.

The sorted array sits along the top with its indices. Each step block shows where lo and hi point and the sum they make. The panel beside it shows whether we saved a triplet or moved a pointer.

Follow the colour cues as you read it.

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

Some people read pictures faster than tables. Use whichever version clicks for you, or sketch your own while you follow the code.

8. Comparing the Three Approaches

All three give the same correct answer. They just pay very different prices for it.

Notice the two faster versions share the same time class. The real separator is memory and cleanliness. The two-pointer sweep carries almost nothing, and its duplicate handling reads as two small skips.

In an interview, start with brute force to show you understand the goal. Then point out the wasted third loop. Finally tighten it into the sort-and-two-pointer sweep and explain the two duplicate guards.

That climb from slow to lean is exactly the story interviewers want. Jumping straight to the optimal answer skips the reasoning they came to watch.

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.

javahandson.com | DSA Series | Arrays & Strings