[Leetcode 15] 3Sum in JavaScript By using two pointers algorithm. (DP)
3Sum is medium level question in LeetCode.
The question is “Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. The solution set must not contain duplicate triplets.”
It has given a test case:
There is a solution which is the two-pointers method or double-pointers method.The solving path of the method should start by targeting each element of the array and find its combinations with other elements in the array.
So we need a loop here.
But before we jump into the iteration, let’s think about how can we optimize its algorithm performance, for example, we can cut all the unnecessary loopings. Sorting out the elements’ value in ascending order will be ideal. But Why?
Let me give you an example:
If we don’t sort out the array, each element needs to check with all other elements, so there will C(n, 3) combinations, which is the cube of a number n or n to the third power. We sort out the array, then we can use a condition to cut out some of the work, which is related to our solution later.
So the first step is to sort out the array by ascending order.
After the sorting, the test case will be: [-4, -1, -1, 0,1, 2]. Now we can start the iteration for each element.
The reason we only iterate to the third last element is that we need to leave the last two items to combine with the third element from the end of the array into a sum for evaluation.
Before we start our pointer moving process, let’s image some scenarios, we also call the edge cases, for example, if the test case contains all negative or all positive integers, do we still need to waste our time to do further evaluations?
The answer is No!
So we can implement that as below.
Ok, now it’s time to start our fun pointer moving process. Like I mentioned before, the method we are using called the two-pointers process. So that means there will be two pointers to help us track the values in each looping.
Our goal is to find combinations that produce “sum === 0”, we have sorted out our array in this stage, so that means the numbers on the left side will always be smaller than the numbers on the right side, in order to achieve our result, we need to start with the smallest number and the biggest number.
Since the iteration element will always become the smallest number, the item next to the iteration element will take the role to balance the pointing process as the negative impact in the process. During the evaluation, the iteration element will be in the static state.
So now let’s declare two pointers: leftPointer = i + 1 and rightPointer = numbers.length-1.
Finally, we can start evaluating combinations of three elements, by the way, the code above is not just good for this problem, it also can apply to similar combination problems from the index-based array data structure. At the same time, we need to use a condition to make sure the left pointer indexed element and the right pointer indexed element will not be the same element since we are working with three elements each time.
After we got the sum, we can start to analyze the value and produce different outcomes according to the value.
There will be three scenarios:
- The sum value is greater than 0.
- The sum value is less than 0.
- The sum value is equal to 0.
If the outcome is the first scenario, that means the sum is a positive value, and we need to reduce the sum value by moving the right pointer to the left by 1 index position. Vice versa, If the outcome is scenario 2, that means the sum is a negative value, and we need to increase the sum value by moving the left pointer to the right side by 1 index position.
If the outcome is the final scenario, that means we found out the target outcome, and we should ‘remember’ it into an array, so that we can return the array eventually.
Once we found a set of target combinations, it’s time to reset our pointers right away. First, we need to find out if the next element for pointers has the same value as the current element since the same value element will produce the same result. Since in this case, we have found the right set, for the next evaluation, we need to change both pointers with brand new values to produce potential right set. If we change one pointer with a brand new value, that will produce an incorrect set since a singular value will break the balance in the process in which the sum is already equal to 0 at the moment. That’s why we need to double check the next elements’ values. At the same time, we also need to maintain the (leftPointer < rightPointer) status to make the algorithm valid.
To this point, I guess you would say this algorithm is perfect! But the truth is I intentionally missed a step, or you can say a detail in the problem, please read the last sentence.
The solution set must not contain duplicate triplets.
Yes, we need to make sure there are no duplicate triplets. when you execute your code right now with the test case, you will get [[-1,-1,2],[-1,0,1],[-1,0,1]], why? The reason is that the second and the third element’s values both are ‘-1’ in our test case after the sorting. So that means we evaluate the ‘-1’ base element twice which that will produce the duplicate triplets. Ok, if in that case, let’s write a condition to avoid that scenario:
if(numbers[i] === numbers[i +1]) continue;
Sorry, the evaluation above is still wrong, now we do have a condition to eliminate duplicated evaluation; however, the elimination position is incorrect. When you skip the left element instead of the right element, you potentially altered the following calculation for the sum with the rest of the items in the array. Alternatively, if you evaluate the right one, the potential risk has been eliminated since you have already assessed the value from the left one.
So the final solution should be like this:
By using two pointers approach, we reduce the time complexity from n to the third power to n to the second power.
Let me know if you have any questions about this method, or if you have an any better approach to this problem.
Stay happy. Stay coding.