https://leetcode.com/problems/3sum/

I always struggle with this problem 🙂

Even when I have solved it multiple times – the reasoning behind the solution is simple enough, the tricky part for me is always getting rid of duplicates.

The basic idea is simple – choose one number and then try to find two additional numbers such that all three numbers combined – their sum is 0.

Now, with 2 Sum solved – we already know how to find two numbers that add up to a specific number (in this case, target – firstNumber). So the trick to this question is to first choose a number and then use the 2 Sum solution to find the other two numbers.

It is possible to solve this without sorting, but I find sorting + two pointer approach much simpler to reason and code in an interview setup.

So my solution – sorts the array first, ‘chooses’ a non-duplicate number as possible part of triplet – and then tries to find two more numbers (by using two pointer approach) that add up to 0. If we do find a triplet that meets the criteria – we need to be careful to ignore all neighbors that are the same number.

This gets us the O(N^2) time solution. Based on the language used, the time complexity varies, however Swift sort uses tim sort which takes O(N) space to sort an array.