3Sum

Medium Arrays & Hashing Two Sum Original on LeetCode

3Sum is a medium arrays & hashing problem solved with the two sum pattern. The best approach, optimal (sort + two pointers), runs in O(n²) time and O(1) space. Below are 2 approaches in Java, from brute force up.

Problem

Given an integer array nums, return every unique triplet [a, b, c] of values taken from three different indices where a + b + c == 0.

The answer must not contain the same triplet twice, even if the array has repeated values.

Examples

Example 1

Input: nums = [-2, 0, 1, 1, 2]
Output: [[-2, 0, 2], [-2, 1, 1]]
Why: Both triplets sum to 0. Order inside the output does not matter.

Example 2

Input: nums = [0, 0, 0, 0]
Output: [[0, 0, 0]]
Why: Many index choices give the same triplet; it is listed once.

Example 3

Input: nums = [1, 2, -1]
Output: []

Constraints

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Brute force	`O(n³)`	`O(k)`
Optimal (sort + two pointers)	`O(n²)`	`O(1)`

1Brute force

TimeO(n³)n choose 3 triplets.

SpaceO(k)The set of k unique answers.

Check every triplet of indices. Sort each triplet and add it to a set so duplicates collapse.

Three nested loops over i < j < k.
If the three values sum to 0, sort them and add the list to a set.
Return the set as a list.

Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> found = new HashSet<>();
        int n = nums.length;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                for (int k = j + 1; k < n; k++)
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> t = Arrays.asList(nums[i], nums[j], nums[k]);
                        Collections.sort(t);
                        found.add(t);
                    }
        return new ArrayList<>(found);
    }
}

2Optimal (sort + two pointers)

TimeO(n²)Sorting is O(n log n); the outer loop runs n times and each two-pointer scan is O(n).

SpaceO(1)Extra space apart from the output (and the sort's own stack).

Sort the array. For each index i, find pairs in the rest of the array that sum to -nums[i] with two pointers moving inward. Skip equal neighbours so each triplet is produced once.

Sort nums.
For each i, skip it if nums[i] equals nums[i - 1]; stop once nums[i] > 0.
Set lo = i + 1 and hi = n - 1.
If the sum is too small move lo right, too big move hi left.
On a match, record it, then move both pointers past equal values.

Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> out = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            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 {
                    out.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 out;
    }
}

Edge cases to test

All zeros
No valid triplet
Many duplicates of the same value

Hints

Hint 1

Fix one number. What problem is left for the other two?

Hint 2

Sorting makes both the two-pointer search and duplicate skipping easy.

FAQ

What is the best time complexity for 3Sum?

Optimal (sort + two pointers) runs in O(n²) time and O(1) extra space. Sorting is O(n log n); the outer loop runs n times and each two-pointer scan is O(n).

Which pattern does 3Sum use?

It is a arrays & hashing problem that uses the two sum pattern. Other problems with the same pattern: Two Sum.

Is there a brute force solution for 3Sum?

Yes. Brute force takes O(n³) time and O(k) space. Check every triplet of indices.

Which edge cases should I test for 3Sum?

All zeros; No valid triplet; Many duplicates of the same value.