3Sum

Signal

A sum condition over three elements instead of two, with "no duplicate triplets" in the ask. That last clause is the tell: it's pushing you toward sorting first, both to enable two pointers and to make duplicate-skipping mechanical instead of something you track in a set.

Approach

Sort the array. Fix one element at index i and look for two more that cancel it out — that's Two Sum II on the remaining slice, solved with two pointers converging from i + 1 and the end. After sorting, equal values sit next to each other, so skipping past duplicates at any of the three positions is just "if this value equals the previous one, move on."

Skeleton

sort(nums)
for i in range(len(nums)):
    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:
            record [nums[i], nums[left], nums[right]]
            skip duplicates at left and right; left += 1; right -= 1
        elif total < 0: left += 1
        else: right -= 1

Solution

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    for i in range(len(nums)):
        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:
                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

Complexity

O(n²) time — an O(n) two-pointer sweep inside an O(n) outer loop, plus the O(n log n) sort which doesn't dominate. O(1) extra space beyond the output (sorting in place).

Pitfalls

• Skipping duplicates only at the outer loop and forgetting the inner left/ right skips — you'll get correct triplets but with repeats in the output.
• Skipping duplicates before recording a match instead of after — you'd silently drop a valid triplet.
• Reaching for a hash-set-of-tuples to dedupe after the fact — it works but is strictly more code and memory than the sorted-array skip trick above.