3Sum
Return all unique triplets whose sum is zero.
Return all unique triplets whose sum is zero. The real pattern is sorting once, then turning the inner search into a two-pointer sweep.
Pattern fit
Sorting turns the inner pair search into a controllable two-pointer scan, while the outer loop anchors one number at a time.
Key observation
Once the array is sorted, the remaining two numbers must move based on whether the current sum is too small or too large.
Target complexity
O(n^2) / O(1)
How to break down the solution cleanly
Sort the array so duplicate handling and pointer movement both become manageable.
Fix one number at index i and reduce the problem to a two-sum search on the suffix.
Use left and right pointers to search for the remaining two values.
Skip duplicates at both the outer loop and inner pointer levels.
Walk through one example
Example: [-1, 0, 1, 2, -1, -4] becomes [-4, -1, -1, 0, 1, 2].
Fix -1 at index 1, then search the suffix with left = 2 and right = 5.
You find [-1, -1, 2] and [-1, 0, 1], skipping duplicates as you move.
No other anchors add new unique triplets.
Reference implementation
Pythondef threeSum(nums: list[int]) -> list[list[int]]:
nums.sort()
answer: list[list[int]] = []
for index in range(len(nums) - 2):
if index > 0 and nums[index] == nums[index - 1]:
continue
left, right = index + 1, len(nums) - 1
while left < right:
total = nums[index] + nums[left] + nums[right]
if total == 0:
answer.append([nums[index], 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 answer
Common pitfalls
Forgetting duplicate skipping at the outer or inner level.
Failing to sort first, which destroys pointer meaning.
Common follow-ups
How would you adapt this to target = k?
Where exactly do duplicates need to be skipped and why?
Continue with related problems
Build repeatable depth inside the Two Pointers cluster before moving on.