3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.

The output should not contain any duplicate triplets. You may return the output and the triplets in any order.

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].

The only possible triplet does not sum up to 0.

The only possible triplet sums up to 0.

Approach

Sort the array, then fix one number nums[i] and use two pointers (left, right) to find pairs that sum to -nums[i]. Skip duplicate values for i and also skip duplicates after finding a valid triplet. This ensures the output contains unique triplets and handles cases like all zeros.

Why It Works

After sorting, all pairs for a fixed i are scanned in linear time by moving the two pointers based on whether the current sum is too small or too large. Sorting also groups equal values, so skipping duplicates prevents repeated triplets. Every valid triplet appears exactly once in this scan.

Complexity

• Time: O(n^2)
• Space: O(1) extra (excluding output)

Reference Implementation (Python)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        n = len(nums)

        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, n - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif total < 0:
                    left += 1
                else:
                    right -= 1
        return result