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

Viewed 7178

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(N2)?


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.

11 Answers
Related