Minimize Max of Three Different Sorted Arrays in C++

Concept

With respect of given three sorted arrays A, B, and C of not necessarily same sizes,compute the lowest i.e. minimum absolute difference between the maximum and minimum number of any triplet A[i],B[j], C[k] such that they are under arrays A, B and C respectively, i.e., minimize (max(A[i], B[j], C[k]) – min(A[i], B[j], C[k])).

Input−

A : [ 2, 5, 6, 9, 11 ]
B : [ 7, 10, 16 ]
C : [ 3, 4, 7, 7 ]

Output−

1

Explanation

When we select A[i] = 6 , B[j] = 7, C[k] = 7, we get the minimum difference as max(A[i], B[j], C[k]) - min(A[i], B[j], C[k])) = |7-6| = 1

Input−

A = [ 6, 9, 11, 16 ]
B = [ 7, 10, 16, 79, 90 ]
C = [ 3, 4, 7, 7, 9, 9, 11 ]

Output−

1

Explanation−

When we select A[i] = 11 , b[j] = 10, C[k] = 11. we get the minimum difference as max(A[i], B[j], C[k]) - min(A[i], B[j], C[k])) = |11-10| = 1

Method

Begin with the highest elements in each of the arrays A, B & C. Track a variable to update the answer at the time of each of the steps to be followed.

With respect of each and every step, the only possible way to lessen the difference is to lessen the maximum element out of the three elements.

As a result of this, visit to the next highest element in the array containing the maximum element for this step and update the answer variable.

We have to repeat this step until and unless the array containing the maximum element terminates.

Example(C++)

// C++ code for above approach

 Live Demo

#include<bits/stdc++.h>
usingnamespacestd;
intsolve(intA1[], intB1[], intC1[], inti1, intj1, intk1) {
intmin_diff, current_diff, max_term;
// calculating min difference from last
// index of lists
min_diff = abs(max(A1[i1], max(B1[j1], C1[k1]))
- min(A1[i1], min(B1[j1], C1[k1])));
while(i1 != -1 && j1 != -1 && k1 != -1) {
   current_diff = abs(max(A1[i1], max(B1[j1], C1[k1]))
   - min(A1[i1], min(B1[j1], C1[k1])));
   // checking condition
   if(current_diff < min_diff)
      min_diff = current_diff;
      // calculating max term from list
      max_term = max(A1[i1], max(B1[j1], C1[k1]));
      if(A1[i1] == max_term)
         i1 -= 1;
      elseif(B1[j1] == max_term)
         j1 -= 1;
      else
         k1 -= 1;
   }
   returnmin_diff;
}
intmain() {
   intD1[] = { 5, 8, 10, 15 };
   intE1[] = { 6, 9, 15, 78, 89 };
   intF1[] = { 2, 3, 6, 6, 8, 8, 10 };
   intnD = sizeof(D1) / sizeof(D1[0]);
   intnE = sizeof(E1) / sizeof(E1[0]);
   intnF = sizeof(F1) / sizeof(F1[0]);
   cout << solve(D1, E1, F1, nD-1, nE-1, nF-1);
   return0;
}

Output

1