[Java] FourSum

Similar to ThreeSum, but this time we need to find all unique quadruples that sum up to a given target.

I think if we were required to only count all possible quadruples, we could do this in O(N^2) time and space, but finding all unique quadruples means discarding already used elements and since our array can contain duplicates I think O(N^3) is what we can do.

We use a class Quadruple that stores four integers, we also define a hashCode and equals so that if all elements in different quadruples are same, no matter in which order they appear, then we consider the quadruples same.

I thought about XORing all values in both objects, then ANDing them and check if result is 0, but negative elements are allowed, therefore we get a wrong result (at least in Java with the 2's complement representation of negatives). I ended up adding elements of both objects to two sets, then comparing the sets for equality.

The approach to solve the problem is scanning the array in O(N^2) time to generate all sums of two elements, and track them in a map where the key is the sum and the value is the list of all pairs with that sum in the form (element1, element2, index1, index2).

This also gives O(N^2) space usage.

Then we scan again the array and for each pair we check if the map contains the complement we need: target - sum of pair.

If it does, we scan the list of pairs to remove duplicates (other pairs that have at least one index in common with the current pair), then add the result to the output only if we have not seen that quadruple already (store it in a set).

Total time is O(N^3) and space is O(N^2).

Of critical importance is the implementation of hashCode and equals for the Quadruple class since the set will deduplicate ONLY if it can verify equality.

Maybe an approach similar to the second option of threeSums where we sort the array first, then do the two nested loops with a third loop on the remaining portion of the array could give O(N^2) time if we still use O(N) or O(N^2) extra space, but I couldn't figure it out.

You can check my implementation of fourSum on my Gist along with some lazy tests in FourSumJTests.