3Sum

MediumTwo PointersBlind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given an integer array nums. Return every triplet [nums[i], nums[j], nums[k]] where i, j and k are three different indices and the values sum to 0. The result must not contain duplicate triplets: triplets with the same values count once, even if they come from different indices. The triplets, and the values inside each one, may be in any order. Return an empty list if there are none.

Examples

nums = [-1,0,1,2,-1,-4] returns [[-1,-1,2],[-1,0,1]]

(-1) + (-1) + 2 = 0 uses both -1s, and (-1) + 0 + 1 = 0 can be built from either -1 but is listed once. No triplet includes -4, because the two largest values, 1 and 2, only add up to 3.

nums = [0,1,1] returns []

The only possible triplet is 0 + 1 + 1 = 2, which isn't 0.

nums = [0,0,0] returns [[0,0,0]]

The three zeros sit at different indices, so they form a valid triplet even though the values are equal.

Constraints

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

Hints

Hint 1

Could you reduce this to repeatedly solving a simpler 2-sum problem on a sorted array?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Sort nums. For each index i, treat nums[i] as the smallest value and look for a pair summing to -nums[i] after it, with one index at each end moving inward depending on whether the sum is too small or too large. Skip an i whose value equals the previous one, and after each hit step both ends past repeated values, so each triplet is emitted once. Stop once nums[i] > 0. Extra space is O(1) beyond the sort and the output.

Time

O(n^2)

Space

O(1)

Pitfall

Skip a repeated first value by comparing nums[i] with nums[i - 1], not nums[i + 1]. Comparing with the next value skips the first -1 in [-4,-1,-1,0,1,2] and loses [-1,-1,2].

Solutions

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; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < 0) left++;
                else right--;
            }
        }
        return result;
    }
}

class Solution:
    def threeSum(self, nums):
        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:
                s = nums[i] + nums[left] + nums[right]
                if s == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif s < 0:
                    left += 1
                else:
                    right -= 1
        return result