Find the Quadruplets - Hard

Problem - Given 4 arrays A,B,C,D. Find out if there exists an instance where A[i] + B[j] + C[k] + D[l] = 0

Like the Find the Triple problem, we're going to develop 4 algorithms to solve this. Starting with the naive O(n^4) solution.

	// Complexity - O(n^4)
	private int[] findQuad_1(int[] A, int[] B, int[] C, int[] 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++)
	for (int l = 0, dl = D.length; l < dl; l++)
	if (A[i] + B[j] + C[k] + D[l] == 0) return new int[]{A[i], B[j], C[k], D[l]};
	return null;
	}

view raw FindQuadruplet.java hosted with ❤ by GitHub

Then we proceed to eliminate the inner-most loop with a Binary Search, reducing the complexity to O(n^3 logn)

	// 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;
	}

view raw FindQuadruplet.java hosted with ❤ by GitHub

Now, we replace the last 2 loops with the left-right traversal we did in the previous 3 posts.

Now the complexity is O(n^3).

	// Complexity - O(n^3)
	private int[] findQuad_3(int[] A, int[] B, int[] C, int[] D) {
	Arrays.sort(C);
	Arrays.sort(D);
	int cl = C.length, dl = D.length;
	for (int i = 0, al = A.length; i < al; i++) {
	for (int j = 0, bl = B.length; j < bl; j++) {
	int left = 0, right = dl - 1;
	while (left < cl && right >= 0) {
	int s = A[i] + B[j] + C[left] + D[right];
	if (s == 0)
	return new int[]{A[i], B[j], C[left], D[right]};
	if (s < 0)
	left++;
	else
	right--;
	}
	}
	}
	return null;
	}

view raw FindQuadruplet.java hosted with ❤ by GitHub

Finally, we reduce the complexity to O(n^2 logn) at the cost of O(n^2) Space Complexity. We store every combination of A[i] + B[j] and store it in AB[]. Similarly we make CD[] out of C[i] + D[j].

	// Complexity - O(n^2 logn), Space Complexity - O(n^2)
	private int[] findQuad_4(int[] A, int[] B, int[] C, int[] D) {
	Integer[] AB = new Integer[A.length * B.length];
	Integer[] CD = new Integer[C.length * D.length];
	for (int i = 0, l = AB.length; i < l; i++) AB[i] = i;
	for (int i = 0, l = CD.length; i < l; i++) CD[i] = i;
	Arrays.sort(AB, new IndexComparator(A, B)); // O(n^2 logn)
	Arrays.sort(CD, new IndexComparator(C, D)); // O(n^2 logn)
	int left = 0, abl = AB.length, right = CD.length - 1;
	int bl = B.length, dl = D.length;
	while (left < abl && right >= 0) { // O(n^2)
	int leftIndex = AB[left], rightIndex = CD[right];
	int s = A[leftIndex / bl] + B[leftIndex % bl] + C[rightIndex / dl] + D[rightIndex % dl];
	if (s == 0)
	return new int[]{A[leftIndex / bl], B[leftIndex % bl], C[rightIndex / dl], D[rightIndex % dl]};
	else if (s < 0)
	left++;
	else
	right--;
	}
	return null;
	}
	private class IndexComparator implements Comparator<Integer> {
	private int[] X, Y;
	private int yl;
	private IndexComparator(int[] x, int[] y) {
	X = x;
	Y = y;
	yl = Y.length;
	}
	@Override
	public int compare(Integer o1, Integer o2) {
	return X[o1 / yl] + Y[o1 % yl] <= X[o2 / yl] + Y[o2 % yl] ? -1 : 1;
	}
	}

view raw FindQuadruplet.java hosted with ❤ by GitHub

So,

AB = A x B
CD = C x D

We then sort AB and CD (which costs O(n^2 log(n^2)) ~ O(n^2 logn) ) and then run a left-right linear Algorithm on AB and CD. (Note : Their size is of the order O(n^2))

So the overall complexity is due to sorting the large array of size n^2. which is O(n^2 logn).