3Sum

Medium Problem 19 of 151 Java and Python

Problem

Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] such that i, j and k are different indices and nums[i] + nums[j] + nums[k] == 0.

The answer must not contain duplicate triplets. The order of the triplets, and of the numbers inside each, does not matter.

Example 1

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Why: These are the only two distinct triplets that add up to 0.

Example 2

Input: nums = [0, 1, 1]
Output: []

Example 3

Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]

Constraints

3 ≤ nums.length ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵

Explanation

Fix the first number a. You now need two numbers that sum to -a, which is Two Sum II, solved with two pointers once the array is sorted.

Sorting also makes duplicates easy to skip: equal values sit together, so skip a value if it equals the one before it in the same role.

Approach 1 · Naive

Every triplet, deduplicated with a set

Time O(n³)
Space O(number of triplets)

Try every combination of three indices. Sort each matching triplet and put it in a set so duplicates collapse.

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

Java

import java.util.*;

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> triplet = Arrays.asList(nums[i], nums[j], nums[k]);
                        Collections.sort(triplet);
                        found.add(triplet);
                    }
                }
            }
        }
        return new ArrayList<>(found);
    }
}

Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        found = set()
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        found.add(tuple(sorted((nums[i], nums[j], nums[k]))))
        return [list(t) for t in found]

Approach 2 · Optimal

Sort, then two pointers

Time O(n²)
Space O(1) extra besides the output (sorting may use O(log n))

Sort the array. For each i, look for pairs in i + 1 … n - 1 that add to -nums[i] with two pointers, skipping repeated values.

Sort nums.
For each i: if nums[i] > 0, stop (no three positives sum to 0). Skip i if nums[i] == nums[i - 1].
Set left = i + 1, right = n - 1. Move them inwards like Two Sum II.
On a match, record it, move both pointers, and keep moving left while it repeats the previous value.

Java

import java.util.*;

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

Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        for i in range(len(nums) - 2):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, len(nums) - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    result.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
        return result

Complexity compared

Approach	Time	Space
Naive Every triplet, deduplicated with a set	O(n³)	O(number of triplets)
Optimal Sort, then two pointers	O(n²)	O(1) extra besides the output (sorting may use O(log n))

Key takeaways

k-Sum problems reduce to (k – 1)-Sum by fixing one number, down to two pointers.
Skip duplicates in both places: the fixed number and the left pointer after a match.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem