Problem intuition
- The brute-force approach checks every triple and deduplicates with a set.
- The better route sorts first, fixes one number, and then solves the remaining pair with two pointers while skipping duplicates.
Solution
The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.
Solution 1
Triple nested loops with a set
- Try every triplet and check whether the sum is zero.
- Sort each chosen triple locally and use a set to remove duplicates.
- This is correct, but it is still expensive.
- Time complexity: O(n^3)
- three nested loops enumerate every possible triplet before checking its sum.
- Space complexity: O(k)
- the set stores the unique triplets you discover, which grows with the output size.
Solution 2
Sort and solve remaining pair with two pointers
- Sort once and fix one number at a time.
- Use two pointers for the remaining pair and skip duplicates as you move.
- Time complexity: O(n^2)
- for each fixed index, the left and right pointers scan the remaining array only once.
- Space complexity: O(1) extra excluding output
- aside from the answer list, the algorithm reuses the sorted array and a few pointer variables.