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

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²).

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.