Find the Triple - Hard

Problem : Given 3 Integer Arrays A,B,C. Find out if an instance exists where A[i] + B[j] + C[k] == 0.

Very deceptive question but very similar to the 3SUM Problem. The Naive solution is O(n^3). If you're a little clever, you can do a O(n^2 logn). At this point, you might give up assuming that this is pretty efficient. But then there is also a O(n^2) solution as well!

Let's go from worst to best.

The Naive solution is trivial.

	FIND-TRIPLET-1(A,B,C)
	FOR i = 1 to len(A)
	FOR j = 1 to len(B)
	FOR k = 1 to len(C)
	if A[i] + B[j] + C[k] == 0
	RETURN {A[i],B[j],C[k]}
	RETURN {}
	END-FUNCTION

view raw gistfile1.txt hosted with ❤ by GitHub

Try every combination until we hit a solution, if we don't there is no solution.

So let's try to speed things up a bit, since the solution is already O(n^3), I think we can afford to sort any of the  arrays since nlogn = o(n^3). Therefore, we cleverly sort the Array C. Now in the third loop we replace the linear scan with a binary search to find (-A[i]-B[j]). The complexity is now reduced to O(n^2 logn)

	FIND-TRIPLET-2(A,B,C)
	SORT(C)
	FOR i = 1 to len(A)
	FOR j = 1 to len(B)
	k = BINARY-SEARCH(C,-A[i]-B[j])
	if k > 0
	RETURN {A[i],B[j],C[k]}
	RETURN {}
	END FUNCTION

view raw gistfile1.txt hosted with ❤ by GitHub

At this point, you've leveled up. The next algorithm might not be immediately apparent but works. In fact the method is similar to the O(n^2) solution to 3SUM.

	FIND-TRIPLET-3(A,B,C) // A[1..len(A)]
	SORT(A)
	SORT(B)
	FOR i = 1 to len(C)
	left = 1
	right = len(B)
	WHILE left <= len(A) AND right > 0
	SUM = A[left] + B[right] + C[i]
	IF SUM == 0
	return {A[left] , B[right] , C[i]}
	ELSE IF SUM < 0
	left = left + 1
	ELSE
	right = right - 1
	END-WHILE
	RETURN {}
	END FUNCTION

view raw gistfile1.txt hosted with ❤ by GitHub

Java Code for all these solutions can be found here.