3Sum

Finding triplets that sum to zero is a foundational exercise in two-pointer techniques, sorting, and careful duplicate handling. The “3Sum” problem tests your ability to combine sorting with pointer sweeps to achieve O(n²) performance.

Problem Statement

Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c = 0. Triplets must be in non-descending order internally, and duplicate triplets must be omitted.

Example:
Input: nums = [-1,0,1,2,-1,-4]
Output: [
  [-1, -1, 2],
  [-1,  0, 1]
]

1. Clarify Requirements Before Jumping Into Code

First let's start by confirming some details:

• Triplets must sum exactly to zero.

• We must return unique triplets with no duplicates.

• Internal order of each triplet should be non-decreasing.

• The overall collection can be in any order.

2. Identify the Category of the Question

This sounds like an extension of the classic 2Sum problem, and I remember the 2Sum problem can be solved with a two-pointer technique. We can assume a similar pattern may come into play here as well. Some rough ideas:

• Will sorting come in to play somehow? Maybe

• Is there some way I can simplify the problem so that I'm only comparing pairs instead of triplets?

• Maybe skipping duplicate values may help to avoid duplicate triplets

3. Consider a Brute-Force Approach to Understand the Problem

For a brute-force solution: we could have three nested loops i < j < k, and as I iterate through each loop, I'll check if nums[i] + nums[j] + nums[k] == 0. Then, collect all the triplets and deduplicate.

• Time Complexity: O(n³)

4. Brainstorm More Solutions

Option 1: Hash-based two-pointer

The 3Sum problem sounds pretty similar to the 2Sum problem, so I wonder, can I solve this problem by building on that solution?

As we saw in a previous post, the 2Sum problem is best solved with a two-pointer solution. If I want to use two pointers for the 3Sum problem as well, then at any point in my loop through the array, I'd know at least two of the values of my triplet. But that begs the question - how do I know what the third value of my triplet should be?

In real life, I could solve that with some basic arithmetic.

If a + b + c = 0, and I know the values of a and b, then I can calculate the value of c pretty easily.

But I don't need to just solve for c, I need to know if c exists in my array. And, I need to be able to make that determination in constant time, so as to avoid a third run through the array that would increase my runtime to O(n³).

What if I use a different data structure to store the elements of my array - one that can tell me in constant-time whether or not the element exists?

A hash-map would give me the constant time look-up. The key for my hash-map could be my array elements, and the value would be the number of times that element appears in my array (so I don't accidentally reuse the same element multiple times)!

So my logic would look something like:

• Iterate one through the array to populate my hash-map in O(n) time.

• Then, use a nested loop to compare every pair of elements i and j.

• Calculate c (0 - nums[i] - nums[j]) and check if it exists in my hash-map. If yes, then I have a triplet!

• This give me a runtime of O(n²).

• Triplet deduplication is tricky though. The only way to know for sure would be to compare every triplet against every other triplet. That's pretty inefficient, but luckily it won't increase my runtime past O(n²).

Option 2 - Sort + two-pointer

If I continue with this idea of building on the two-pointer solution, I end up coming back to the same question I asked earlier - how can I quickly determine if there is a third element in my array that will complete my triplet?

Part of the reason my brute-force solution has to iterate through the entire input to find that third element is because that element could be anywhere in my array. But what if I could be more easily predict where in my input array that third element is located? What if my elements were sorted?

This brings me back to another solution for the 2Sum problem, one that can only be applied when you have a sorted array. Sorting guarantees I know exactly how my sum is going to change when I increment/decrement my pointers. Because of this, the 2Sum problem actually has an O(n) solution when the input array is sorted: if my sum is too large, I decrement my top pointer; and if my sum is too small, then I increment my bottom pointer. I keep moving pointers inward until I either find a pair that matches my target, or my pointers cross.

It's also much easier to ensure I'm not creating duplicate triplicates when duplicate elements in the array are sitting right next to each other. I can skip elements that are identical since they don't add anything new to the result set.

Now what about that third element? Rather than trying to rework the two-pointer solution for a sorted array, what if I just used that third element as an anchor? I'll loop through the array and give every element the opportunity to be my anchor (let's call it i), and then I'll use the 2Sum solution on the rest of the elements to see if I can find two elements that equals 0 - nums[i]. That should work! And it gives me O(n²) time.

And how can I use the fact that an array is sorted to prevent duplicates?

Well, as I'm incrementing i, if I come across an element i that is the same as the previous element, then I can just skip it, because we'll just end up with the same set of solutions as the previous iteration of i.

Additionally, when I find a triplicate that equals 0, then on the next iteration, I can move both pointers inward (since moving just one is guaranteed to fail). I'll also make sure to skip over any duplicate elements, since that will lead to a duplicate triplet.

Putting this all together:

• Sort the array

• For each element i (from 0 to n-2):

  • if nums[i] == nums[i-1] (and i > ), skip

  • leftPointer = i+1, rightPointer = n-1

  • while left < right: calculate nums[i] + nums[leftPointer] + nums[rightPointer]

    • If it equals 0, add the triplicate to my solution set, then increment the left pointer and decrement the right pointer, skipping over duplicate elements

    • If the sum is too large, decrement the rightPointer to decrease the sum

    • If the sum is too small, increment the leftPointer to increase the sum

This gives me a solution that is O(n²) time and O(1) extra space. It also has the advantages of automatically handling duplicates, and is a cleaner solution overall

5. Discuss Trade-Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Triple nested loops	O(n³)	O(1)	Simple	Very inefficient
Hash-based 2Sum per i	O(n²)	O(n)	Avoids sorting	More complex deduplication
Sort + two-pointer	O(n²)	O(1)	Clean, widely known pattern	Must handle duplicates carefully

6. Write Pseudocode to Structure Your Thoughts

sort(nums)
result = []
for i from 0 to n-3:
  if i > 0 and nums[i] == nums[i-1]: continue
  left = i+1, right = n-1
  while left < right:
    sum = nums[i] + nums[left] + nums[right]
    if sum == 0:
      add [nums[i], nums[left], nums[right]] to result
      left++, right--
      skip duplicates at left and right
    else if sum < 0:
      left++
    else:
      right--
return result

7. Consider Edge Cases

• Fewer than three elements → return empty.

• All zeros → one triplet [0,0,0].

• No valid triplets → return empty.

• Large positive or negative values → sorting handles it.

8. Write Full Code Syntax

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3) return res;
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++; right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }
}

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.threeSum(new int[]{-1,0,1,2,-1,-4}));
    // expected [[-1,-1,2],[-1,0,1]]

    System.out.println(sol.threeSum(new int[]{0,0,0,0}));
    // expected [[0,0,0]]

    System.out.println(sol.threeSum(new int[]{1,2,-2,-1}));
    // expected []

    System.out.println(sol.threeSum(new int[]{-2,0,1,1,2}));
    // expected [[-2,0,2],[-2,1,1]]

    System.out.println(sol.threeSum(new int[]{}));
    // expected []
}

10. Key Lessons to Remember for Future Questions

• Sorting plus two-pointer is a powerful O(n²) pattern for K-sum when K=3.

• Simplifying the question allowed us to recall and expand on solutions we already knew for the 2Sum problem

• This can be expanded even further, to a 4Sum or KSum problem. You would need nested loops or recursion, but they use the same two-pointer core solution