3SUM Swirl

Question

I received this question in an interview and was not sure how to answer. This is a regular 3SUM problem, and we all know the answer is O (n ^ 2). The question goes like this: you have 3 unsorted arrays a, b, c. Find three elements such that a [i] + b [j] + c [k] = 0. You are not allowed to use hashing in this scenario, and the solution should be <= O (n ^ 2)

Here is my answer and yes, it's 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; } } } } } 

Does anyone have any brilliant ideas to solve this less than or equal to O (N ^ 2)?

Thanks!

Answer 1

Sort A and Sort B.

As soon as we sort, taking into account S, in O (n) time, we can solve the problem of finding i, j such that A [i] + B [j] = S.

We can do this by supporting the two pointers a and b, initially at the lowest element A and b at the largest. Then you increase or decrease b, respectively, after comparing A [a] + B [b] with S.

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