Interview question: three arrays and O(N*N)

Question

Assume we have three arrays of length N which contain arbitrary numbers of type long. Then we are given a number M (of the same type) and our mission is to pick three numbers A, B and C one from each array (in other words A should be picked from first array, B from second one and C from third) so the sum A + B + C = M.

Question: could we pick all three numbers and end up with time complexity of O(N²)?

---

Illustration:

Arrays are:

1) 6 5 8 3 9 2 2) 1 9 0 4 6 4 3) 7 8 1 5 4 3 

And M we've been given is 19. Then our choice would be 8 from first, 4 from second and 7 from third.

Answer 1

This can be done in O(1) space and O(N²) time.

First lets solve a simpler problem:
Given two arrays A and B pick one element from each so that their sum is equal to given number K.

Sort both the arrays which takes O(NlogN).
Take pointers i and j so that i points to the start of the array A and j points to the end of B.
Find the sum A[i] + B[j] and compare it with K

• if A[i] + B[j] == K we have found the pair A[i] and B[j]
• if A[i] + B[j] < K, we need to increase the sum, so increment i.
• if A[i] + B[j] > K, we need to decrease the sum, so decrement j.

This process of finding the pair after sorting takes O(N).

Now lets take the original problem. We've got a third array now call it C.

So the algorithm now is :

foreach element x in C   find a pair A[i], B[j] from A and B such that A[i] + B[j] = K - x end for 

The outer loop runs N times and for each run we do a O(N) operation making the entire algorithm O(N²).

Answer 2

You can reduce it to the similar problem with two arrays, which is kinda famous and has simple O(n) solution (involving iterating from both ends).

1. Sort all arrays.
2. Try each number A from the first array once.
3. Find if the last two arrays can give us numbers B and C, such that B + C = M - A.

Steps 2 and 3 multiplied give us O(n^2) complexity.