Tech Qu: Finding the minimum of the maximum difference.

Given 3 arrays A,B,C find three indices i,j,k such that the value of I = max((a-b),(b-c),(c-a)) is minimized.

i.e.

• a = A[i]
• b = B[j]
• c = C[k]

This is one of those problems that you can accidentally head down a rabbit hole. Remember the KISS principle. Instead of trying to do an elegant solution, write a direct solution and then attempt optimize it if need be.

 

Code Snippet

1. public static string MinOf3Arrays(int[] a, int[] b, int[] c)
2.     {
3.       var results = "no result";
4.       var min = int.MaxValue;
5.       foreach (var ai in a)
6.         foreach (var bi in b)
7.           foreach (var ci in c)
8.           {
9.             var max = Math.Max(Math.Max(ai - bi, bi - ci), ci - ai);
10.             if (max < min)
11.             {
12.               min = max;
13.               results = string.Format("{3} Min from: A@i={0}, B@j={1}, C@k={2}", ai, bi, ci, min);              
14.             }
15.           }
16.       return results;
17.     }

 

And a simple test:

Code Snippet

1. int[] a = { 8, 19, 31, 38, 65, 85, 110, 150 };
2. int[] b = { 24, 51, 90, 130, 140, 180, 190, 220, 250, 260 };
3. int[] c = { 24, 51, 90, 130, 140, 180, 190, 220, 250, 260 };      
4. Console.WriteLine(Questions.MinOf3Arrays(a, b, c));

The answer came out as:
5 Min from: A@i=19, B@j=24, C@k=24

Seeing the answer suggests that the maximum minimum difference between elements of two arrays is what you need to search for. Deducing this algorithm from the statement would be very difficult for most people, but once the first solution is done and tested, it can be seen easily. This would reduce the search time:

• from a.Length * b.Length * c.Length 
• to a.Length* b.Length + a.Length*c.Length+ b.Length*c.length

If a,b,c are known to be sorted, then we can further improve performance to

• to (a.Length+ b.Length) + (a.Length+c.Length)+ (b.Length+c.length)

With a little more complex coding, you can half this again to:

• a.Length+ b.Length + c.Length