3Sum

Problem Given an integer array, return all unique triplets [a, b, c] with a + b + c = 0. The solution set must not contain duplicate triplets.

Input / Output

• Input: int array nums.
• Output: list of unique zero-sum triplets.

Constraints

• 3 <= n <= 3000; O(n^2) expected — the O(n^3) brute force is the warm-up only.

Example

• nums = [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]]

Expected approach

• Sort, then fix the first element i and run two pointers (lo = i+1, hi = n−1) on the remainder: move lo/hi by sum comparison, record hits, and skip equal neighbours at i, lo, and hi to dedupe. Prune when nums[i] > 0. O(n^2) time, O(1) extra space. Know the variants: 3Sum-closest, 4Sum (extra outer loop), and the hash-set alternative per fixed i.