Find three closest elements from given three sorted arrays - GeeksforGeeks
Given three sorted arrays A[], B[] and C[], find 3 elements i, j and k from A, B and C respectively such that max(abs(A[i] – B[j]), abs(B[j] – C[k]), abs(C[k] – A[i])) is minimized. Here abs() indicates absolute value.
Example :
Input: A[] = {1, 4, 10} B[] = {2, 15, 20} C[] = {10, 12} Output: 10 15 10 10 from A, 15 from B and 10 from C Input: A[] = {20, 24, 100} B[] = {2, 19, 22, 79, 800} C[] = {10, 12, 23, 24, 119} Output: 24 22 23 24 from A, 22 from B and 23 from C We strongly recommend you to minimize your browser and try this yourself first.
A Simple Solution is to run three nested loops to consider all triplets from A, B and C. Compute the value of max(abs(A[i] – B[j]), abs(B[j] – C[k]), abs(C[k] – A[i])) for every triplet and return minimum of all values. Time complexity of this solution is O(n3)
A Better Solution is to us Binary Search.
1) Iterate over all elements of A[],
a) Binary search for element just smaller than or equal to in B[] and C[], and note the difference.
2) Repeat step 1 for B[] and C[].
3) Return overall minimum.
Time complexity of this solution is O(nLogn)
Read full article from Find three closest elements from given three sorted arrays - GeeksforGeeks
No comments:
Post a Comment