3SUM With a twist

Question

I got asked this question in an interview and was not sure how to answer. This is a regular 3SUM problem and we all know the O(n^2) answer. Question goes this way: You have 3 non-sorted arrays a, b, c. Find three element such that a[i] + b[j] + c[k] = 0. You are not allowed to use hashing in this scenario and the solution must be <= O(n^2)

Here is my answer and yes this is still O(n^3) unfortunately

public static void get3Sum(int[] a, int[] b, int[] c) {
    int i = 0, j = 0, k = 0, lengthOfArrayA = a.length, lengthOfArrayB = b.length, lengthOfArrayC = c.length;

    for (i = 0; i < lengthOfArrayA; i++) {
        j = k = 0;
        while (j < lengthOfArrayB) {
            if (k >= lengthOfArrayC) {
                j++;
                continue;
            } else if (a[i] + b[j] + c[k] == 0) {
                // found it: so print
                System.out.println(a[i] + " " + b[j] + " " + c[k]);
                k++;
                if (j > lengthOfArrayB - 1)
                    break;

            } else {
                k++;
                if (k >= lengthOfArrayC) {
                    j++;
                    k = 0;
                }

            }
        }
    }
}

Anyone has any brilliant ideas to solve this in less then or equal to O(N^2)?

Thanks!

Answer 1

Sort A and Sort B.

Once we sort, given an S, in O(n) time, we can solve the problem of finding i,j such that A[i] + B[j] = S.

This we can do by maintaining two pointers a and b, a initially at the lowest element of A, and b at the largest. Then you increment a or decrement b appropriately after comparing A[a] + B[b] with S.

For your problem, run the O(n) algorithm n times (so O(n^2)) by taking S to be all -C[k].