3SUM - Hard

Problem - Given an Array of integers, A. Find out if there exists a triple (i,j,k) such that A[i] + A[j] + A[k] == 0.

The 3SUM problem is very similar to the 2SUM problem in many aspects. The solutions I'll be discussing are also very similar. I highly recommend you read the previous post first, since I'll explain only the differences in the algorithm from the previous post.

Let's begin, We start with the naive algorithm. An O(n^3) solution with 3 nested loops each checking if the sum of the triple is 0. Since O(n^3) is the higher order term, we can sort the array in O(nlogn) and add a guard at the nested loops to prune of parts of the arrays. But the complexity still remains O(n^3).

The code is pretty simple and similar to the naive algorithm of 2SUM.

	// Complexity - O(n^3)
	private int[] findTriple_1(int[] A) {
	Arrays.sort(A); // O(nlogn)
	for (int i = 0, l = A.length; i < l && A[i] < 0; i++) {
	for (int j = i + 1; j < l && A[i] + A[j] < 0; j++) {
	for (int k = j + 1; k < l; k++) {
	int s = A[i] + A[j] + A[k];
	if (s > 0) break;
	if (s == 0) return new int[]{A[i], A[j], A[k]};
	}
	}
	}
	return null;
	}

view raw ThreeSum.java hosted with ❤ by GitHub

Moving on, we'll do the same thing we did in 2SUM, replace the inner-most linear search with a binary search. The Complexity now drops to O(n^2 logn)

	// Complexity - O(n^2 logn)
	private int[] findTriple_2(int[] A) {
	Arrays.sort(A); // O(nlogn)
	for (int i = 0, l = A.length; i < l && A[i] < 0; i++) { //O(n^2 logn)
	for (int j = i + 1; j < l && A[i] + A[j] < 0; j++) {
	int k = Arrays.binarySearch(A, j + 1, l, -A[i] - A[j]);
	if (k > j) return new int[]{A[i], A[j], A[k]};
	}
	}
	return null;
	}

view raw ThreeSum.java hosted with ❤ by GitHub

Now, the hash table method, this is strictly not the same as the previous problem, here we have to store the pair associated with the sum, hence I switch to a HashMap instead of a set. Also we need to store the pairs for each i and clear the map when we pick a new starting element.

	// Complexity - O(n^2), Space Complexity - O(n^2)
	private int[] findTriple_3(int[] A) {
	Map<Integer, int[]> map = new HashMap<Integer, int[]>();
	for (int i = 0, l = A.length; i < l; i++) {
	map.clear();
	for (int j = i + 1; j < l; j++) {
	if (map.containsKey(A[j])) {
	int[] pair = map.get(A[j]);
	return new int[]{pair[0], pair[1], A[j]};
	} else
	map.put(-A[i] - A[j], new int[]{A[i], A[j]});
	}
	}
	return null;
	}

view raw ThreeSum.java hosted with ❤ by GitHub

 Note. This time we don't need the array to sorted. We can do it ourselves, since our overall complexity is going to be O(n^2), a sort call will only cost us O(nlogn) which is a lower order term.

And now finally, we're going to use the left-right method (for lack of a better name).This time we keep one element as a constant and then for each element A[i], we run the 2SUM Linear Algorithm for A[i+1...n] That gives us a O(n^2) algorithm.

	// Complexity - O(n^2)
	private int[] findTriple_4(int[] A) {
	Arrays.sort(A);
	for (int i = 0,l = A.length; i < l; i++) {
	int left = i + 1, right = l - 1;
	while (left < right) {
	int s = A[i] + A[left] + A[right];
	if (s == 0)
	return new int[]{A[i],A[left], A[right]};
	else if (s > 0)
	right--;
	else
	left++;
	}
	}
	return null;
	}

view raw ThreeSum.java hosted with ❤ by GitHub

The Entire source code can be found here.