### Find three elements from three sorted arrays sortedarray array searching    Posted: 5 years ago Updated: 4 years ago Edit answers (1) views (2795)

Suppose you are given 3 sorted arrays. Find three elements ( a , b , c ), one from each array, such that a + b = c .

 Posted: 5 years ago 0 0 Edit Let the three given sorted arrays be array1 [ ], array2 [ ] and array3 [ ]. Take the first element of the array3 . Take pointers i and j so that i points to the start of the array1 and j points to the end of array2 . Calculate array1[i] + array2[j] and compare it with array3[0] . If array1[i] + array2[j] == array3[0] , we have found the pair array1[i] , array2[j] and array3[0] . If array1[i] + array2[j] < array3[0] , increment i . If array1[i] + array2[j] > array3[0] , decrement j . Repeat the above steps for all the elements of array3 [ ]. Time complexity = $$O(\underbrace{Length\ of\ array3}_{Outer\ for\ loop} \times \underbrace{(Length\ of\ array1+Length\ of\ array2)}_{Inner\ while\ loop})$$For simplicity, if we assume all the three arrays are of same length, say n , overall time complexity will be $$O(n^{2})$$.