Find all unique triplets in the array that add up to 0. The same triplet must not appear twice in the answer.
DSA Animator › DSA Revision › Arrays › 3Sum
Remember: sort, fix one number, two pointers for the other two. Skip equal neighbours to avoid duplicate triplets. The video solves 3Sum (LeetCode 15, Medium) with the Sort + Two Pointers pattern from the Arrays topic, and you can replay every step in the interactive 3Sum animation.
Find all unique triplets in the array that add up to 0. The same triplet must not appear twice in the answer.
For minus 1, 0, 1, 2, minus 1, minus 4, the answer is two triplets. They are minus 1, minus 1, 2, and minus 1, 0, 1.
Three nested loops check every triplet in O of n cubed. And you would still have to remove duplicate triplets afterwards.
First sort the array. Fix one number, then find the other two with two pointers, just like Two Sum 2. If the sum is too small, move the left pointer right, and if it is too big, move the right pointer left. Skip any value equal to the one before it, so no triplet repeats.
Sorted, the array is minus 4, minus 1, minus 1, 0, 1, 2. Fix minus 4: even the two largest numbers, 1 and 2, only reach minus 1, so there is no triplet. Fix the first minus 1: minus 1 plus 2 makes 0 with it, so minus 1, minus 1, 2 is a triplet. Move both pointers inward: 0 and 1 also make 0, so minus 1, 0, 1 is a triplet. The next minus 1 is the same value as before, so we skip it. Fix 0: 1 plus 2 is 3, which is too big, and the pointers meet. That gives exactly two triplets.
In code, sort, then loop i, skipping a value equal to the previous one. Set left after i and right at the end, and compare the three-number sum with 0. On a match, record the triplet, then skip duplicates on both sides and move both pointers. Sorting is O of n log n and the loops are O of n squared, so it's O of n squared time.
Remember: sort, fix one number, two pointers for the other two. Skip equal neighbours to avoid duplicate triplets.