Find three closest elements from given three sorted arrays - GeeksforGeeks

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.

Note that we increment the pointer of the array which has the minimum, because our goal is to decrease the difference. Increasing the maximum pointer increases the difference. Increase the second maximum pointer can potentially increase the difference.

void findClosest(int A[], int B[], int C[], int p, int q, int r)

{

 

    int diff = INT_MAX;  // Initialize min diff

 

    // Initialize result

    int res_i =0, res_j = 0, res_k = 0;

 

    // Traverse arrays

    int i=0,j=0,k=0;

    while (i < p && j < q && k < r)

    {

        // Find minimum and maximum of current three elements

        int minimum = min(A[i], min(B[j], C[k]));

        int maximum = max(A[i], max(B[j], C[k]));

 

        // Update result if current diff is less than the min

        // diff so far

        if (maximum-minimum < diff)

        {

             res_i = i, res_j = j, res_k = k;

             diff = maximum - minimum;

        }

 

        // We can't get less than 0 as values are absolute

        if (diff == 0) break;

 

        // Increment index of array with smallest value

        if (A[i] == minimum) i++;

        else if (B[j] == minimum) j++;

        else k++;

    }

 

    // Print result

    cout << A[res_i] << " " << B[res_j] << " " << C[res_k];

}

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