Open In App

Find three closest elements from given three sorted arrays

Last Updated : 26 Oct, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

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
Explanation: 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
Explanation: 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.

Steps to implement-

  • Declared three variables a,b, and c to store final answers
  • Initialized a variable “ans” with the Maximum value
  • We will store a minimum of max(abs(A[i] – B[j]), abs(B[j] – C[k]), abs(C[k] – A[i])) in “ans” variable
  • Run three nested loops where each loop is for each array
  • From that loop if max(abs(A[i] – B[j]), abs(B[j] – C[k]), abs(C[k] – A[i])) is less than a minimum of max(abs(A[i] – B[j]), abs(B[j] – C[k]), abs(C[k] – A[i])) present in “ans”
    • Then, update “ans” with new max(abs(A[i] – B[j]), abs(B[j] – C[k]), abs(C[k] – A[i])) and that three variable a,b,c with three elements of those arrays
  • In the last print value present in a,b,c

Code-

C++




// C++ program to find 3 elements such that max(abs(A[i]-B[j]),
//abs(B[j]-C[k]), abs(C[k]-A[i])) is minimized.
 
#include<bits/stdc++.h>
using namespace std;
 
void findClosest(int A[], int B[], int C[], int p, int q, int r)
{
    //Three variable to store answer
    int a,b,c;
     
    //To Store minimum of max(abs(A[i]-B[j]),abs(B[j]-C[k]),
    //abs(C[k]-A[i]))
    int ans=INT_MAX;
 
    //Run three nested loop
    for(int i=0;i<p;i++){
        for(int j=0;j<q;j++){
            for(int k=0;k<r;k++){
                int curr=max(abs(A[i]-B[j]),abs(B[j]-C[k]));
                int temp=max(curr,abs(C[k]-A[i]));
                //If that is minimum than previous then update answer
                if(temp<ans){
                    ans=temp;
                    a=A[i];
                    b=B[j];
                    c=C[k];
                }
            }
        }
    }
     
    //Printing final answer
    cout<<a<<" "<<b<<" "<<c<<endl;
     
}
 
// Driver program
int main()
{
    int A[] = {1, 4, 10};
    int B[] = {2, 15, 20};
    int C[] = {10, 12};
 
    int p = sizeof A / sizeof A[0];
    int q = sizeof B / sizeof B[0];
    int r = sizeof C / sizeof C[0];
 
    findClosest(A, B, C, p, q, r);
    return 0;
}


Java




// Java program to find 3 elements such that
// max(abs(A[i]-B[j]),
// abs(B[j]-C[k]), abs(C[k]-A[i])) is minimized.
 
import java.util.Arrays;
 
public class GFG {
 
    public static void findClosest(int[] A, int[] B,
                                   int[] C, int p, int q,
                                   int r)
    {
        // Three variable to store answer
        int a = 0, b = 0, c = 0;
 
        // To Store minimum of
        // max(abs(A[i]-B[j]),abs(B[j]-C[k]),
        // abs(C[k]-A[i]))
        int ans = Integer.MAX_VALUE;
 
        // Run three nested loop
        for (int i = 0; i < p; i++) {
            for (int j = 0; j < q; j++) {
                for (int k = 0; k < r; k++) {
                    int curr
                        = Math.max(Math.abs(A[i] - B[j]),
                                   Math.abs(B[j] - C[k]));
                    int temp = Math.max(
                        curr, Math.abs(C[k] - A[i]));
 
                    // If that is minimum than previous then
                    // update answer
                    if (temp < ans) {
                        ans = temp;
                        a = A[i];
                        b = B[j];
                        c = C[k];
                    }
                }
            }
        }
        // Printing final answer
        System.out.println(a + " " + b + " " + c);
    }
    // Driver program
    public static void main(String[] args)
    {
        int[] A = { 1, 4, 10 };
        int[] B = { 2, 15, 20 };
        int[] C = { 10, 12 };
 
        int p = A.length;
        int q = B.length;
        int r = C.length;
 
        findClosest(A, B, C, p, q, r);
    }
}


Python3




# Python program to find 3 elements such that max(abs(A[i]-B[j]),
# abs(B[j]-C[k]), abs(C[k]-A[i])) is minimized.
 
def findClosest(A, B, C, p, q, r):
    # Three variables to store answer
    a, b, c = None, None, None
 
    # To store the minimum of max(abs(A[i]-B[j]), abs(B[j]-C[k]),
    # abs(C[k]-A[i]))
    ans = float('inf')
 
    # Run three nested loops
    for i in range(p):
        for j in range(q):
            for k in range(r):
                curr = max(abs(A[i]-B[j]), abs(B[j]-C[k]))
                temp = max(curr, abs(C[k]-A[i]))
                # If that is minimum than previous, then update answer
                if temp < ans:
                    ans = temp
                    a, b, c = A[i], B[j], C[k]
 
    # Printing final answer
    print(a, b, c)
 
# Driver program
A = [1, 4, 10]
B = [2, 15, 20]
C = [10, 12]
 
p = len(A)
q = len(B)
r = len(C)
 
findClosest(A, B, C, p, q, r)
 
# by phasing17


C#




using System;
 
class Program
{
    static void FindClosest(int[] A, int[] B, int[] C, int p, int q, int r)
    {
        // Three variables to store the answer
        int a = 0, b = 0, c = 0;
 
        // To store the minimum of max(abs(A[i]-B[j]), abs(B[j]-C[k]), abs(C[k]-A[i]))
        int ans = int.MaxValue;
 
        // Run three nested loops
        for (int i = 0; i < p; i++)
        {
            for (int j = 0; j < q; j++)
            {
                for (int k = 0; k < r; k++)
                {
                    int curr = Math.Max(Math.Abs(A[i] - B[j]), Math.Abs(B[j] - C[k]));
                    int temp = Math.Max(curr, Math.Abs(C[k] - A[i]));
 
                    // If that is minimum than previous then update answer
                    if (temp < ans)
                    {
                        ans = temp;
                        a = A[i];
                        b = B[j];
                        c = C[k];
                    }
                }
            }
        }
 
        // Printing the final answer
        Console.WriteLine($"{a} {b} {c}");
    }
 
    static void Main(string[] args)
    {
        int[] A = { 1, 4, 10 };
        int[] B = { 2, 15, 20 };
        int[] C = { 10, 12 };
 
        int p = A.Length;
        int q = B.Length;
        int r = C.Length;
 
        FindClosest(A, B, C, p, q, r);
    }
}
 
// This code is contributed by shivamgupta310570


Javascript




// JS program to find 3 elements such that max(abs(A[i]-B[j]),
//abs(B[j]-C[k]), abs(C[k]-A[i])) is minimized.
 
function findClosest(A, B, C, p, q, r)
{
    //Three variable to store answer
    let a,b,c;
     
    //To Store minimum of max(abs(A[i]-B[j]),abs(B[j]-C[k]),
    //abs(C[k]-A[i]))
    let ans = Number.MAX_VALUE;
 
    //Run three nested loop
    for(let i=0;i<p;i++){
        for(let j=0;j<q;j++){
            for(let k=0;k<r;k++){
                let curr=Math.max(Math.abs(A[i]-B[j]),Math.abs(B[j]-C[k]));
                let temp=Math.max(curr,Math.abs(C[k]-A[i]));
                //If that is minimum than previous then update answer
                if(temp<ans){
                    ans=temp;
                    a=A[i];
                    b=B[j];
                    c=C[k];
                }
            }
        }
    }
     
    //Printing final answer
    console.log(a+ " " + b+ " " + c);
     
}
 
// Driver program
let A = [1, 4, 10];
let B = [2, 15, 20];
let C = [10, 12];
 
let p = A.length;
let q = B.length;
let r = C.length;
 
findClosest(A, B, C, p, q, r);


Output-

10 15 10

Time complexity :O(N3),because of three nested loops
Auxiliary space: O(1),because no extra space has been used

A Better Solution is to use 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)

Efficient Solution Let ‘p’ be size of A[], ‘q’ be size of B[] and ‘r’ be size of C[]  

1)   Start with i=0, j=0 and k=0 (Three index variables for A,
B and C respectively)
// p, q and r are sizes of A[], B[] and C[] respectively.
2) Do following while i < p and j < q and k < r
a) Find min and maximum of A[i], B[j] and C[k]
b) Compute diff = max(X, Y, Z) - min(A[i], B[j], C[k]).
c) If new result is less than current result, change
it to the new result.
d) Increment the pointer of the array which contains
the minimum.

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. 

C++




// C++ program to find 3 elements such that max(abs(A[i]-B[j]), abs(B[j]-
// C[k]), abs(C[k]-A[i])) is minimized.
 
#include<bits/stdc++.h>
using namespace std;
 
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];
}
 
// Driver program
int main()
{
    int A[] = {1, 4, 10};
    int B[] = {2, 15, 20};
    int C[] = {10, 12};
 
    int p = sizeof A / sizeof A[0];
    int q = sizeof B / sizeof B[0];
    int r = sizeof C / sizeof C[0];
 
    findClosest(A, B, C, p, q, r);
    return 0;
}


Java




// Java program to find 3 elements such
// that max(abs(A[i]-B[j]), abs(B[j]-C[k]),
// abs(C[k]-A[i])) is minimized.
import java.io.*;
 
class GFG {
     
    static void findClosest(int A[], int B[], int C[],
                                  int p, int q, int r)
    {
        int diff = Integer.MAX_VALUE; // 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 = Math.min(A[i],
                          Math.min(B[j], C[k]));
            int maximum = Math.max(A[i],
                          Math.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
        System.out.println(A[res_i] + " " +
                           B[res_j] + " " + C[res_k]);
    }
 
    // Driver code
    public static void main (String[] args)
    {
        int A[] = {1, 4, 10};
        int B[] = {2, 15, 20};
        int C[] = {10, 12};
     
        int p = A.length;
        int q = B.length;
        int r = C.length;
     
        // Function calling
        findClosest(A, B, C, p, q, r);
    }
}
 
// This code is contributed by Ajit.


Python3




# Python program to find 3 elements such
# that max(abs(A[i]-B[j]), abs(B[j]- C[k]),
# abs(C[k]-A[i])) is minimized.
import sys
 
def findCloset(A, B, C, p, q, r):
 
    # Initialize min diff
    diff = sys.maxsize
 
    res_i = 0
    res_j = 0
    res_k = 0
 
    # Traverse Array
    i = 0
    j = 0
    k = 0
    while(i < p and j < q and k < r):
 
        # Find minimum and maximum of
        # current three elements
        minimum = min(A[i], min(B[j], C[k]))
        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 = i+1
        elif B[j] == minimum:
            j = j+1
        else:
            k = k+1
 
    # Print result
    print(A[res_i], " ", B[res_j], " ", C[res_k])
 
# Driver Program
A = [1, 4, 10]
B = [2, 15, 20]
C = [10, 12]
 
p = len(A)
q = len(B)
r = len(C)
 
findCloset(A,B,C,p,q,r)
 
# This code is contributed by Shrikant13.


C#




// C# program to find 3 elements
// such that max(abs(A[i]-B[j]),
// abs(B[j]-C[k]), abs(C[k]-A[i]))
// is minimized.
using System;
 
class GFG
{
    static void findClosest(int []A, int []B,
                            int []C, int p,
                            int q, int r)
    {
        // Initialize min diff
        int diff = int.MaxValue;
     
        // 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 = Math.Min(A[i],
                          Math.Min(B[j], C[k]));
            int maximum = Math.Max(A[i],
                          Math.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
        Console.WriteLine(A[res_i] + " " +
                          B[res_j] + " " +
                          C[res_k]);
    }
 
    // Driver code
    public static void Main ()
    {
        int []A = {1, 4, 10};
        int []B = {2, 15, 20};
        int []C = {10, 12};
     
        int p = A.Length;
        int q = B.Length;
        int r = C.Length;
     
        // Function calling
        findClosest(A, B, C, p, q, r);
    }
}
 
// This code is contributed
// by anuj_67.


Javascript




<script>
     // JavaScript program to find 3 elements
     // such that max(abs(A[i]-B[j]), abs(B[j]-
     // C[k]), abs(C[k]-A[i])) is minimized.
 
     function findClosest(A, B, C, p, q, r)
     {
       var diff = Math.pow(10, 9); // Initialize min diff
 
       // Initialize result
       var res_i = 0,
         res_j = 0,
         res_k = 0;
 
       // Traverse arrays
       var i = 0,
         j = 0,
         k = 0;
       while (i < p && j < q && k < r)
       {
        
         // Find minimum and maximum of current three elements
         var minimum = Math.min(A[i], Math.min(B[j], C[k]));
         var maximum = Math.max(A[i], Math.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
       document.write(A[res_i] + " " + B[res_j] + " " + C[res_k]);
     }
 
     // Driver program
     var A = [1, 4, 10];
     var B = [2, 15, 20];
     var C = [10, 12];
 
     var p = A.length;
     var q = B.length;
     var r = C.length;
 
     findClosest(A, B, C, p, q, r);
      
     // This code is contributed by rdtank.
   </script>


PHP




<?php
// PHP program to find 3 elements such
// that max(abs(A[i]-B[j]), abs(B[j]-
// C[k]), abs(C[k]-A[i])) is minimized.
 
function findClosest($A, $B, $C, $p, $q, $r)
{
 
    $diff = PHP_INT_MAX; // Initialize min diff
 
    // Initialize result
    $res_i = 0;
    $res_j = 0;
    $res_k = 0;
 
    // Traverse arrays
    $i = 0;
    $j = 0;
    $k = 0;
    while ($i < $p && $j < $q && $k < $r)
    {
        // Find minimum and maximum of
        // current three elements
        $minimum = min($A[$i], min($B[$j], $C[$k]));
        $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
    echo $A[$res_i] , " ", $B[$res_j],
                      " ", $C[$res_k];
}
 
// Driver Code
$A = array(1, 4, 10);
$B = array(2, 15, 20);
$C = array(10, 12);
 
$p = sizeof($A);
$q = sizeof($B);
$r = sizeof($C);
 
findClosest($A, $B, $C, $p, $q, $r);
 
// This code is contributed by Sach_Code
?>


Output: 

10 15 10

Time complexity of this solution is O(p + q + r) where p, q and r are sizes of A[], B[] and C[] respectively.
Auxiliary space: O(1) as constant space is required.

Approach 2: Using Binary Search:

Another approach to solve this problem can be to use binary search along with two pointers.

First, sort all the three arrays A, B, and C. Then, we take three pointers, one for each array. For each i, j, k combination, we calculate the maximum difference using the absolute value formula given in the problem. If the current maximum difference is less than the minimum difference found so far, then we update our result.

Next, we move our pointers based on the value of the maximum element among the current i, j, k pointers. We increment the pointer of the array with the smallest maximum element, hoping to find a smaller difference.

The time complexity of this approach will be O(nlogn) due to sorting, where n is the size of the largest array.

Here’s the code for this approach:

C++




#include<bits/stdc++.h>
using namespace std;
 
void findClosest(int A[], int B[], int C[], int p, int q, int r)
{
 
    sort(A, A+p);
    sort(B, B+q);
    sort(C, C+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]));
 
        // Calculate the maximum difference for the current combination
        int curDiff = abs(maximum - minimum);
 
        // Update result if current diff is less than the min
        // diff so far
        if (curDiff < diff)
        {
            res_i = i, res_j = j, res_k = k;
            diff = curDiff;
        }
 
        // If the maximum element of A is the smallest among the three,
        // we move the A pointer forward
        if (A[i] == minimum && A[i] <= B[j] && A[i] <= C[k]) i++;
 
        // If the maximum element of B is the smallest among the three,
        // we move the B pointer forward
        else if (B[j] == minimum && B[j] <= A[i] && B[j] <= C[k]) j++;
 
        // If the maximum element of C is the smallest among the three,
        // we move the C pointer forward
        else k++;
    }
 
    // Print result
    cout << A[res_i] << " " << B[res_j] << " " << C[res_k];
}
 
// Driver program
int main()
{
    int A[] = {1, 4, 10};
    int B[] = {2, 15, 20};
    int C[] = {10, 12};
 
    int p = sizeof A / sizeof A[0];
    int q = sizeof B / sizeof B[0];
    int r = sizeof C / sizeof C[0];
 
    findClosest(A, B, C, p, q, r);
    return 0;
}


Java




import java.util.*;
 
public class Main {
public static void findClosest(int[] A, int[] B, int[] C, int p, int q, int r) {
      Arrays.sort(A);
    Arrays.sort(B);
    Arrays.sort(C);
 
    int diff = Integer.MAX_VALUE; // 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 = Math.min(A[i], Math.min(B[j], C[k]));
        int maximum = Math.max(A[i], Math.max(B[j], C[k]));
 
        // Calculate the maximum difference for the current combination
        int curDiff = Math.abs(maximum - minimum);
 
        // Update result if current diff is less than the min
        // diff so far
        if (curDiff < diff) {
            res_i = i;
            res_j = j;
            res_k = k;
            diff = curDiff;
        }
 
        // If the maximum element of A is the smallest among the three,
        // we move the A pointer forward
        if (A[i] == minimum && A[i] <= B[j] && A[i] <= C[k])
            i++;
 
        // If the maximum element of B is the smallest among the three,
        // we move the B pointer forward
        else if (B[j] == minimum && B[j] <= A[i] && B[j] <= C[k])
            j++;
 
        // If the maximum element of C is the smallest among the three,
        // we move the C pointer forward
        else
            k++;
    }
 
    // Print result
    System.out.println(A[res_i] + " " + B[res_j] + " " + C[res_k]);
}
 
// Driver program
public static void main(String[] args) {
    int[] A = {1, 4, 10};
    int[] B = {2, 15, 20};
    int[] C = {10, 12};
 
    int p = A.length;
    int q = B.length;
    int r = C.length;
 
    findClosest(A, B, C, p, q, r);
}
}


Python3




import sys
 
def find_closest(A, B, C):
    p, q, r = len(A), len(B), len(C)
    A.sort()
    B.sort()
    C.sort()
     
    diff = sys.maxsize
    res_i, res_j, res_k = 0, 0, 0
     
    i = j = k = 0
    while i < p and j < q and k < r:
        minimum = min(A[i], min(B[j], C[k]))
        maximum = max(A[i], max(B[j], C[k]))
         
        cur_diff = abs(maximum - minimum)
        if cur_diff < diff:
            res_i, res_j, res_k = i, j, k
            diff = cur_diff
         
        if A[i] == minimum and A[i] <= B[j] and A[i] <= C[k]:
            i += 1
        elif B[j] == minimum and B[j] <= A[i] and B[j] <= C[k]:
            j += 1
        else:
            k += 1
     
    return [A[res_i], B[res_j], C[res_k]]
 
# Driver program
A = [1, 4, 10]
B = [2, 15, 20]
C = [10, 12]
 
print(find_closest(A, B, C)) # Output: [4, 10, 10]


C#




using System;
 
public class Program
{
    public static int[] FindClosest(int[] A, int[] B, int[] C)
    {
        int p = A.Length;
        int q = B.Length;
        int r = C.Length;
 
        Array.Sort(A);
        Array.Sort(B);
        Array.Sort(C);
 
        int diff = int.MaxValue;
        int res_i = 0, res_j = 0, res_k = 0;
 
        int i = 0, j = 0, k = 0;
        while (i < p && j < q && k < r)
        {
            int minimum = Math.Min(A[i], Math.Min(B[j], C[k]));
            int maximum = Math.Max(A[i], Math.Max(B[j], C[k]));
 
            int curDiff = Math.Abs(maximum - minimum);
 
            if (curDiff < diff)
            {
                res_i = i;
                res_j = j;
                res_k = k;
                diff = curDiff;
            }
 
            if (A[i] == minimum && A[i] <= B[j] && A[i] <= C[k])
            {
                i++;
            }
            else if (B[j] == minimum && B[j] <= A[i] && B[j] <= C[k])
            {
                j++;
            }
            else
            {
                k++;
            }
        }
 
        return new int[] { A[res_i], B[res_j], C[res_k] };
    }
 
    public static void Main()
    {
        int[] A = { 1, 4, 10 };
        int[] B = { 2, 15, 20 };
        int[] C = { 10, 12 };
 
        int[] result = FindClosest(A, B, C);
        Console.WriteLine(string.Join(" ", result));
    }
}


Javascript




// Function to find the closest elements from three sorted arrays
function find_closest(A, B, C) {
  // Get the length of the three arrays
  let p = A.length,
    q = B.length,
    r = C.length;
 
  // Sort the three arrays in non-decreasing order
  A.sort((a, b) => a - b);
  B.sort((a, b) => a - b);
  C.sort((a, b) => a - b);
 
  // Initialize variables to store the minimum difference and the indices
  // of the closest elements
  let diff = Number.MAX_SAFE_INTEGER;
  let res_i = 0,
    res_j = 0,
    res_k = 0;
 
  // Initialize indices to traverse the three arrays
  let i = 0,
    j = 0,
    k = 0;
 
  // Traverse the arrays until we reach the end of any one of them
  while (i < p && j < q && k < r) {
    // Get the minimum and maximum elements from the three arrays
    let minimum = Math.min(A[i], Math.min(B[j], C[k]));
    let maximum = Math.max(A[i], Math.max(B[j], C[k]));
 
    // Calculate the difference between the maximum and minimum elements
    let cur_diff = Math.abs(maximum - minimum);
 
    // Update the variables to store the indices of the closest elements
    // if the current difference is less than the minimum difference
    if (cur_diff < diff) {
      res_i = i;
      res_j = j;
      res_k = k;
      diff = cur_diff;
    }
 
    // Increment the index of the array with the minimum element
    if (A[i] == minimum && A[i] <= B[j] && A[i] <= C[k]) {
      i++;
    } else if (B[j] == minimum && B[j] <= A[i] && B[j] <= C[k]) {
      j++;
    } else {
      k++;
    }
  }
 
  // Return the closest elements from the three arrays
  return [A[res_i], B[res_j], C[res_k]];
}
 
// Driver program
let A = [1, 4, 10];
let B = [2, 15, 20];
let C = [10, 12];
 
// Call the find_closest function with the three arrays and print the result
console.log(find_closest(A, B, C));


OUTPUT:

10 15 10

Time complexity :O(NlogN) 
Auxiliary space: O(1) as constant space is required.

//Thanks to Gaurav Ahirwar for suggesting the above solutions.
 



Previous Article
Next Article

Similar Reads

Generate all possible sorted arrays from alternate elements of two given sorted arrays
Given two sorted arrays A and B, generate all possible arrays such that the first element is taken from A then from B then from A, and so on in increasing order till the arrays are exhausted. The generated arrays should end with an element from B. Example: A = {10, 15, 25} B = {1, 5, 20, 30} The resulting arrays are: 10 20 10 20 25 30 10 30 15 20 1
12 min read
Find the closest pair from two sorted arrays
Given two arrays arr1[0...m-1] and arr2[0..n-1], and a number x, the task is to find the pair arr1[i] + arr2[j] such that absolute value of (arr1[i] + arr2[j] - x) is minimum. Example: Input: arr1[] = {1, 4, 5, 7}; arr2[] = {10, 20, 30, 40}; x = 32Output: 1 and 30Input: arr1[] = {1, 4, 5, 7}; arr2[] = {10, 20, 30, 40}; x = 50 Output: 7 and 40 Find
15+ min read
Find common elements in three sorted arrays
Given three sorted arrays in non-decreasing order, print all common elements in these arrays. Examples:  Input: ar1[] = {1, 5, 10, 20, 40, 80} ar2[] = {6, 7, 20, 80, 100} ar3[] = {3, 4, 15, 20, 30, 70, 80, 120} Output: 20, 80 Input: ar1[] = {1, 5, 5} ar2[] = {3, 4, 5, 5, 10} ar3[] = {5, 5, 10, 20} Output: 5, 5 Recommended PracticeCommon elementsTry
15+ min read
Find three element from given three arrays such that their sum is X | Set 2
Given three sorted integer arrays A[], B[] and C[], the task is to find three integers, one from each array such that they sum up to a given target value X. Print Yes or No depending on whether such triplet exists or not.Examples: Input: A[] = {2}, B[] = {1, 6, 7}, C[] = {4, 5}, X = 12 Output: Yes A[0] + B[1] + C[0] = 2 + 6 + 4 = 12Input: A[] = {2}
9 min read
Given a sorted array and a number x, find the pair in array whose sum is closest to x
Given a sorted array and a number x, find a pair in an array whose sum is closest to x. Examples: Input: arr[] = {10, 22, 28, 29, 30, 40}, x = 54 Output: 22 and 30 Input: arr[] = {1, 3, 4, 7, 10}, x = 15 Output: 4 and 10Naive Approach:- A simple solution is to consider every pair and keep track of the closest pair (the absolute difference between p
15+ min read
Find three element from different three arrays such that a + b + c = sum
Given three integer arrays and a "sum", the task is to check if there are three elements a, b, c such that a + b + c = sum and a, b and c belong to three different arrays. Examples : Input : a1[] = { 1 , 2 , 3 , 4 , 5 }; a2[] = { 2 , 3 , 6 , 1 , 2 }; a3[] = { 3 , 2 , 4 , 5 , 6 }; sum = 9 Output : Yes 1 + 2 + 6 = 9 here 1 from a1[] and 2 from a2[] a
15+ min read
Find three vertices in an N-sided regular polygon such that the angle subtended at a vertex by two other vertices is closest to A
Given an N-sided regular convex polygon and an angle A in degrees, the task is to find any 3 vertices i, j, and k, such that the angle subtended at vertex j by vertex i and k is closest to A. Note: Each vertex is numbered from 1 to N in an anticlockwise direction starting from any vertex. Examples: Input: N = 3, A = 15Output: 2 1 3Explanation:The g
7 min read
Find triplet sum closest to X in a sorted Doubly Linked List (DLL)
Given a sorted doubly linked list of N nodes and an integer X, the task is to find the sum of three nodes in the list which is closest to X. Examples: Input: DLL: -8 ? 2 ? 3 ? 4 ? 5, X = 1Output: 1Explanation: The required three integers {-8, 4, 5} whose sum is 1 and is closest to 1. Input: DLL: 1 ? 2 ? 3 ? 4, X = 3 Output: 6Explanation: The requir
11 min read
Find closest number in Sorted array
Given an array of sorted integers. We need to find the closest value to the given number. Array may contain duplicate values and negative numbers. Examples: Input : arr[] = {1, 2, 4, 5, 6, 6, 8, 9} Target number = 11Output : 99 is closest to 11 in given arrayInput :arr[] = {2, 5, 6, 7, 8, 8, 9}; Target number = 4Output : 55 is closest to 4 in given
15+ min read
Find the pairs of IDs from two arrays having sum less than target closest to it
Given two arrays arr1[] and arr2[] of pairs of the form {ID, value} of size N and M respectively and an integer target, the task is to find all the pairs of IDs from both the arrays such that the sum of the values of the pairs is maximum and has a value at most M. Examples: Input: arr1[] = [[1, 2000], [2, 3000], [3, 2000]], arr2[] = [[1, 2500], [2,
9 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg