3Sum

Problem

Given an integer array, return all unique triplets whose values sum to zero. The answer must not contain duplicate triplets, even when the input contains repeated numbers.

Approach

Sort the array first. That makes duplicates sit next to each other and lets two pointers walk toward the target sum.

Fix one number at a time, then search the rest of the array with a left pointer and a right pointer. If the sum is too small, move the left pointer up; if it is too large, move the right pointer down; if it hits zero, record the triplet and move both.

Skip a fixed number that equals the previous one, and skip repeated left values after a match. That is what keeps the output free of duplicates without needing a set. Once the fixed number is positive, no later triplet can sum to zero, so the loop can stop early.

Solution

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

• Time: O(n²): sorting is O(n log n), and each fixed number runs one linear two-pointer pass.
• Space: O(1) beyond the output, apart from the space the sort uses.

Edge cases

• Fewer than three numbers returns an empty list.
• An array of zeros returns exactly one triplet.
• Heavy duplication, such as many -1 and 2 values, must still produce each triplet once.