st0le
7/1/2013 - 11:11 PM

O(n^3 logn) - Find Quadruplets

O(n^3 logn) - Find Quadruplets

    // Complexity - O(n^3 logn)
    private int[] findQuad_2(int[] A, int[] B, int[] C, int[] D) {
        Arrays.sort(D);
        for (int i = 0, al = A.length; i < al; i++) {
            for (int j = 0, bl = B.length; j < bl; j++) {
                for (int k = 0, cl = C.length; k < cl; k++) {
                    int l = Arrays.binarySearch(D, -(A[i] + B[j] + C[k]));
                    if (l >= 0) return new int[]{A[i], B[j], C[k], D[l]};
                }
            }
        }
        return null;
    }