1

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

We have 3 sorted arrays A, B and C.
We have to find 3 numbers from each A, B and C such that a+b+c = x

One way to do that will be to pick element from A and B and use binary search to find corresponding element in C. Complexity == O(n^2 lgn)

Is there any other way to do this with preferably no extra space and complexity O(n^2) ?

I was thinking of keeping a pointer at A ...now our question reduces to finding elements from B and C such that their sum is (x-a) but got little lost in this approach .

Community
  • 1
  • 1
user401445
  • 1,014
  • 1
  • 16
  • 41
  • how you've estimated complexity of approach ou've mentioned as `n^2*lgn`? – sll Oct 23 '11 at 20:14
  • 2
    Refer this existing question:- **[http://stackoverflow.com/questions/3987264/interview-question-three-arrays-and-onn][1]** [1]:http://stackoverflow.com/questions/3987264/interview-question-three-arrays-and-onn – Siva Charan Oct 23 '11 at 20:15

0 Answers0