3Sum

MediumAmazonGoogleMetaMicrosoftApple

Problem

Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] such that i, j, k are distinct and nums[i] + nums[j] + nums[k] == 0. The solution set must not contain duplicate triplets.

Intuition — the key insight

Sort first. Fix one element nums[i], then use two pointers on the remaining subarray to find pairs summing to -nums[i]. Sorting lets us skip duplicates cleanly — if nums[i] == nums[i-1], we'd get the same triplets again.

Approach

1. Sort the array

Sorting enables two pointers AND makes duplicate skipping trivial.

2. Fix i, two-pointer on rest

For each i from 0 to n-3: skip if nums[i] == nums[i-1] (duplicate). Set lo=i+1, hi=n-1. Move pointers: if sum < 0, lo++; if sum > 0, hi--; if sum == 0, record and skip duplicates on both sides.

Complexity

Time

O(n²)

Space

O(1) extra

Sorting is O(n log n). The outer loop is O(n), inner two-pointer is O(n) — total O(n²). Output space doesn't count as extra.

Solution code

Python

def threeSum(self, nums: List[int]) -> List[List[int]]:
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue  # skip duplicate i
        
        lo, hi = i + 1, len(nums) - 1
        
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                result.append([nums[i], nums[lo], nums[hi]])
                while lo < hi and nums[lo] == nums[lo+1]: lo += 1
                while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
                lo += 1; hi -= 1
    
    return result

Edge cases to remember

⚠All zeros [0,0,0]: valid triplet, return [[0,0,0]]

⚠All positive: no triplet sums to 0 after sorting

⚠Duplicate skipping on i: check i > 0 before comparing nums[i] == nums[i-1]

⚠Duplicate skipping on lo/hi: skip BEFORE moving lo++/hi--

Hints

What pattern do you think this problem uses?