Minimum range of 3 sets

Of course, the brute-force solution described by IVlad is simple and therefore easier and faster to write, but the complexity O(n3)

.

As per your tag, algorithm

I would like to post a more complex algorithm that has worst case O(n2)

and medium complexity O(nlogn)

(almost sure of this, but I'm too lazy to do the proof).

Algorithm Description

Think about some abstract tuples (X, Y, Z)

. We want to find a tuple that has the minimum distance between the maximum and minimum elements. At this point, we can say that the distance is actually created by our maximum element and minimum element. Therefore, the value of the element in between doesn't really matter as long as it really is between the maximum and minimum.

So here's the approach. We allocate some extra set of (call it S

) and combine each initial set of ( X

, Y

, Z

) in one. We also need to be able to search for the original set of each item in the set we just created (so if we point to some item in S

, say S[10]

and ask, "Where did this guy come from?", Our application should respond with something like "It comes from Y

).

After that, let's sort our new set S

using its keys (this will be O (n log n) or O (n) in some specific cases)

Determining the minimum distance

Now for the fun part. What we want to do is compute some artificial value, call it minimum distance and mark it as d[x]

, where X

is some element from S

. This value refers to the minimum distance max - min

that can be achieved using elements that are predecessors / successors of the current element in the sequence.

Consider the following example: this is our set S

(the first line shows the indices, the second shows the values ​​and letters X

, Y

and Z

refers to the initial sets):

0 1 2 3 4  5  6  7
------------------
1 2 4 5 8 10 11 12
Y Z Y X Y  Y  X  Z

      

        
        
        
      

    

Let's say we want to calculate what our minimum distance is for the element at index 4. In fact, this minimum distance means the best tuple (X, Y, Z)

that can be built using the selected element.

In our case ( S[4]

), we can say that our pair (X, Y, Z)

will definitely look like (something, 8, something)

because it must have an element that we are calculating the distance to (pretty obvious, hehe).

Now we have to fill in the blanks. We know that the elements we are looking for must be from X

and Z

. And we want these elements to be the best in terms of distance max - min

. There is an easy way to select them.

We do a bi-directional run (run left, to the right of the current element), looking for the first-not-from- element Y

. In this case, we will search for the two nearest elements from X

and Z

in two directions (4 elements in total).

This search method is what we need: if we select the first element from X

while working (left / right, doesn't matter), that element will be better for us than any other element that follows it in terms of distance. This is because our set is being S

sorted.

In the case of my example (assuming the distance for the item with index number 4

), we will mark items with indices 6

and 7

as suitable on the right side, and items with indices 1

also 3

on the left side.

Now we need to test 4 cases that can happen - and take a case to keep our distance as close as possible. In our specific case, we have the following (elements returned by the previous procedure):

Z  X  Y   X  Z
2  5  8  11 12

      

        
        
        
      

    

We have to test every (X, Y, Z) tuple that can be built using these elements, take the tuple with the minimum distance, and store that distance for our element. In this example, we would say that (11, 8, 12)

tuple has the best distance 4

. So we store d[5] = 4

( 5

the index of the element here).

Satisfying the result

Now that we know how to find the distance, do this for each element of our set S

(this operation will take O(n2)

the worst case and the best time is something like O(nlogn)

average).

Once we have this distance value for each element in our set, simply select the element with the minimum distance and run our distance algorithm (as described above) on it again, but now save the tuple (-, -, -)

. That would be the answer.

pseudocode

There is pseudocode here, I tried to make it easier to read, but the implementation would be more complicated because you would need to code the set * ("define set for element"). Also note that the definition of a tuple and the definition of distance procedures are basically the same, and the second gives the actual tuple.

COMBINE (X, Y, Z) -> S 
SORT(S)

FOREACH (v in S)
   DETERMINE_DISTANCE(v, S) -> d[v]

DETERMINE_TUPLE(MIN(d[v]))

      

        
        
        
      

    

PS

I'm sure this method can be easily used to find (-, -, -, ... -) a tuple, still resulting in good algorithmic complexity.