## What is it? Find all unique triplets in an array that sum to zero. Extension of Two Sum using sorting and two pointers. ## How it works - Sort the array - Iterate with index `i` from 0 to n-3: - Skip duplicates for `i` - Use two pointers `left = i+1`, `right = n-1` - If `arr[i] + arr[left] + arr[right] == 0` → record triplet; skip duplicates; advance both pointers - If sum < 0 → move `left++`; if sum > 0 → move `right--` ## When to use - Three Sum (LeetCode 15) - As a pattern for k-Sum problems (reduce to (k-1) Sum recursively) - Counting/finding triplets with a specific sum ## Key Points - O(n²) time — sorting is O(n log n) dominated by the O(n²) two-pointer phase - O(n) space for sorting (in-place sort uses O(log n)) - Duplicate skipping is critical to avoid repeated triplets in the output - Sorting makes it possible to apply two pointers