Well… I wasn’t born with the talent of a premiership footballer, so this will likely be the only 3sum I get.
This is another Leetcode problem, it builds upon the 2sum example (see the previous post) but adds one more number (obviously) and some more conditions, which significantly increase the difficulty of the problem being solved.
Lets have a look at the problem;
“Given a list of integers return all the triplets which sum to 0, Do not contain duplicates in your output“
And an example showing input and correct output;
Input: [-1,0,1,2,-1,-4] (note you can include the same number multiple times)
Answer: There are 2 distinct triplets which sum to 0
- [1,0,1] – this is because -1 + 0 + 1 = 0
- [-1,-1,2] – this is because -1 + -1 + 2 = 0
Possible Approaches
As demonstrated in the 2sum post the most obvious solution is some kind of brute force approach with 3 loops – checking every possible combination, this will work but is far from efficient.
One other possibility is to take each number in the array and then apply a modified version of the 2sum code on the remaining 2 numbers of each triplet (picking one number – deducting and then applying the 2sum), this would need to be modified as now by design in the problem you can have multiple solution, this is a reasonable approach I suppose, but would lead to a pretty dull post as its kind of repeating what was already done. To solve this problem I think its possible to implement a solution by sorting the numbers and using pointers.
Proposed Solution
Lets say we have the following input array;
It would be useful to have some structure to the array, allowing me to avoid lots of checks at each step. Because of this the first step we will undertake is to sort the array from smallest to largest. This gives me the array below;
One advantage of sorting the array is it allows us to have an idea of what way to “move” in order to get closer to a solution. Lets say we were evaluating the following numbers in our example;
we evaluate that this triplet does not equal 0 (-1 + -1 + 0), but because we have sorted the array we know that in order to make this triplet sum to a larger value (closer to 0) – we need to move to the right
our current position sums to -2 – but the next position sums to -1;
Getting closer to our intended target of 0. Obviously the alternative is true too, if our number is > 0 we can move to the left in our sorted array and reduce the size of the sum.
In order to do this we need three pointers within our list – a left pointer and a right pointer and the current value we iterate on, moving to the left and the right will allow us to increase or decrease the sum.
The following is my initial proposal for how to solve this problem.
- Sort the input array
- Loop through all the numbers in the array
- We will fix the first number in our array in our example -3 and set two pointers – one at the start and end of the sequence as shown below;
- We sum these numbers – in this example this is 1 (-3 + -1 + 5)
- As 1 is greater than 0 we need to either make the value smaller by right pointer left
- We then evaluate the new position;
- In this position our value is 2 (-3 + -1 + 2)
- As 2 is greater than 0 we continue to move the right pointer left
- We keep repeating this until we evaluate all the values (when the pointers meet).
- If there is a sum of 0 we store the answer
- Once we have all our answers we can remove any duplicates
Coding The Solution
The code below is one implementation of this proposal;
we start off by sorting the list – then we loop through this sorted list. The left pointer is the current value, the right pointer is the end of the array.
A while loop is written with the condition to keep looping until the two pointers meet.
The sum of all 3 values (current value, left pointer and right pointer) is taken. If the sum is 0 we have an answer – but continue to look for more by moving the left pointer to the right.
If the sum is less than 0 we increase the left pointer to a higher value, if the sum is greater than zero we decrease the right pointer
The de-duplication takes place by creating a distinct set.
if we run this code on our example;
We show 3 distinct triplets which sum to 0;
Potential Improvements
I think this is a fairly neat way of solving this problem, its also radically different to the 2 sum solution I gave in a previous post, showing how there are many ways you can solve one problem (as we could have re-purposed that to some extent), I think the main area to improve if you cared strongly about performance would be to not de-duplicate the set in the way I am doing here, you could possible come up with a way of the main loop ignoring values it has already seen thereby not performing the same calculation twice, this way you wouldn’t need additional steps to remove potential duplicates as you would never write them. Personally though in my experience in most business applications read-ability is often favoured over performance and I think using a set to de-duplicate the results actually makes the code easier to understand.
The code shown in this post is on GitHub (Leetcode/3Sum)