Find three elements from three sorted arrays
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (2614)

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


Posted Answers

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}) \).

You need to Sign In to post your solution.