• ← Previous
• Next →

Let us go through some of the common 3-sum related problems that can be solved using a two-pointer technique.

Problem: 3Sum

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

Given an array, find all three elements a, b, c such that a + b + c = 0. The combinations need to be unique. Here is the way to do that:

• We sort the input array.
• Next, we process arr[i] (i starts from 0 till N-3, where N is the length of the array).
• When we process arr[i], we find two elements in the right subarray of i (from i+1 till N-1) that equal to -arr[i].
• We do not consider anything left of arr[i] since if that were a candidate, then that would have been considered already.
• The problem can have duplicates. The usual trick to avoid duplicate combinations is being used here as well. If (j != i) && (a[j]==a[i]) then skip. We can also do this when selecting the two elements on the right of arr[i] and so check needs to be pretty thorough!!
• Note that if someone were to ask the same for 2Sum (array has duplicates but return only the unique ones), then we can use the same trick to weed out duplicates as above.

Problem: 3Sum Closest

Problem: https://leetcode.com/problems/3sum-closest/

This is same as 3 Sum. Given an array, find all three elements a, b, c such that a + b + c is closest to the target. Here we do not have to worry about duplicates since this would not affect the final answer.

Problem: 3Sum With Multiplicity

Problem: https://leetcode.com/problems/3sum-with-multiplicity/

Even here, we should try the case, where a[i] is the last element of the three and check in the hashmap that has all elements from 0 to i-1 if there are two elements that add up to K-a[i]. Following that we should add a[i]. Note that since we are checking for two elements, we would still need to avoid the above issue (since we are checking from 0 to i-1 and all elements are already loaded in the hashmap) since there is not much we can do here.

Note that if we were to use HashMap to find two elements, then we do not know if the current element is already being accounted for or not. For example, if array is [2, 1, 0, 100] and we want to check if two elements add up to 4, then since we have already added 2, when we look at 2, we would find that 4-2 already exists. So, to avoid this issue, as we proceed, we add a[i] only after we have checked for K-a[i] in the array.

• ← Previous
• Next →