st0le
7/1/2013 - 9:33 PM

O(n^2) Solution - Triplet

O(n^2) Solution - Triplet

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