Let us go through some of the 4-Sum related problems that are solved using two-pointer technique.
Problem: 4 Sum
Problem: https://leetcode.com/problems/4sum/
Given an array, how many (a,b,c,d) are there in the array such that a + b + c + d = K? The solution set must not contain duplicate quadruplets.
- This is all about optimization since the time-complexity is O(N^3)
- So, this finds 4Sum using 3Sum and that uses 2Sum.
- For the outermost number (this is the a[i] and for this a[i], we need to find three numbers]),
- If (a[i] + 3 * max < target), then skip. This means that even if we were to combine a[i] with all the three max and if the value is still less than target, then that means a[i] is too small.
- If (4 * a[i] > target) break; Because, we have reached an a[i] such that 4 times of a[i] is itself bigger than target -- there is no point calling Has3Sum on this or on any element to the right of a[i].
- Also, to eliminate duplicates, at each layer, if a[i] is same as a[i-1], then we can skip that.
There are some cool optimizations that focus on target being less than being the smallest *K and target being higher than the highest * K:
- In 4Sum, if the target is less than 4 * a[lo] or if target is higher than 4 * a[hi], then we have no solution.
- In 3Sum, if the target is less than 3 * a[lo] or if target is higher than 3 * a[hi], then we have no solution.
- In 2Sum, if the target is less than 2 * a[lo] or if target is higher than 2 * a[hi], then we have no solution.
- So, the above is, in some ways, lesser than the least and higher than the highest approach.
Problem: 4 Sum II
Problem: https://leetcode.com/problems/4sum-ii/
Given 4 lists A, B, C, D, how many tuples (i, j, k, l) have A[i] + B[j] + C[k] + D[l] is zero.
A naive solution would be O(N^4). Here, we can use the unique solution to consider lists (A, B) first and then consider lists (C, D). In doing so, we know that we are processing elements uniquely.
- In this case, we find all pair sums of (A, B) and store it in a hashmap.
- Next, we iterate over all pair sums of (C, D) (say M) -- and for each M, we see if we have (X-M) in the hashmap.
- This reduces the time-complexity to O(N^2) and the space-complexity to O(N+M), where N and M are the lengths of A and B.
This does not apply to "4Sum" since we only one one list. We cannot apply the above here. Let us say, we can, then we can split 4Sum into two lists but what if the 4 elements come from the single list.. So, "4Sum II" is a unique problem since it says that the solution must have one element from each of the list.
Note that this problem is similar to the problem of finding a^3+b^3=c^3+d^3.
- Find (a^3+b^3) for all pairs of (a, b). Then put them in a hashmap.
- Next, find (c^3+d^3) for all pairs of (c, d). Check if they existing the hashmap.