Finding least difference between max and min value of all possible sets of numbers

Question

There are n arrays of k size each.

a0[0],a0[1],......a0[k-1]
a1[0],a1[1],......a1[k-1]
.
.
.
an-1[0],an-1[1], .... an-1[k-1]

There are no duplicates at all and all the arrays are sorted.

Now a Set of size n is constructed by taking any value randomly from each of the arrays. e.g one such set can be {a0[0],a1[3],a2[2],.... an-1[k-1]}.

My goal is to find out the min and max elements in all possible Sets such that the difference between the min and max is the lowest.

Example (k=3,n=3)

[3 7 11]
[1 12 15]
[4 19 21]

So mathematically there will be 27 such sets

(3 1 4) (3 12 4) (3 15 4)
(3 1 19) (3 12 19) (3 15 19)
(3 1 21) (3 12 21) (3 15 21)

(7 1 4) (7 12 4) (7 15 4)
(7 1 19) (7 12 19) (7 15 19)
(7 1 21) (7 12 21) (7 15 21)

(11 1 4) (7 12 4) (11 15 4)
(11 1 19) (7 12 19) (11 15 19)
(11 1 21) (7 12 21) (11 15 21)

After computing min and max values of all these sets we can conclude that (3 1 4) is the set for which difference between min (1) and max (4) is the global minimum or lowest.

So we will output 3 as the global minimum difference and the corresponding pair which is (3 4). If there are multiple global minima then print them all. Please suggest the algorithm with better time and space complexity. We can't go for brute force approach.

Answer 1

Code:

private static ElementData calcMin(int[] n1Arr, int[] n2Arr, int[] n3Arr) {

    ElementData data = new ElementData();// added just to know which two elements algo has picked

    int[] mixArr = { n1Arr[0], n2Arr[0], n3Arr[0] };
    Arrays.sort(mixArr);
    int minValue = mixArr[2] - mixArr[0];

    data.setMinValue(minValue);
    data.setHighValue(mixArr[2]);
    data.setLowValue(mixArr[0]);

    int tempValue = 0;
    for (int n1 : n1Arr) {

        for (int n2 : n2Arr) {

            for (int n3 : n3Arr) {

                int[] mixArr1 = { n1, n2, n3 };
                Arrays.sort(mixArr1);

                tempValue = mixArr1[2] - mixArr1[0];
                if (minValue > tempValue) {
                    minValue = tempValue;

                    data = new ElementData();
                    data.setMinValue(minValue);
                    data.setHighValue(mixArr1[2]);
                    data.setLowValue(mixArr1[0]);
                }
            }
        }
    }
    return data;
}

Answer 2

Complexity of this algorithm is O(n*k*logn)

Select only the first element from each row and create a min heap and a max heap.

Calculate the current difference (=head(maxHeap)-head(minheap))

Remove the head of minHeap (and the corresponding element from maxHeap) and add the next element from the corresponding array (corresponding to removed element) to both minHeap and maxHeap.

Repeat it until all the elements in at one of the array are exhausted.

Complexity: You add/remove nk elements and update takes O(n) time at most. So complexity is O(nklogn).

Note: It is not exactly your stock heap. The minHeap contains pointer to the same element in maxHeap and vice versa. When you delete an element from minHeap, you can find the link to the maxHeap and delete it too. Also whenever position of a particular element changes, appropriate changes are made to the link in the other heap.

Answer 3

Consider the result Set as a simple 1xn array

[3]
[1]
[4]

where the global difference is 3 (maximum of 4 less minimum of 1).

Now consider an expanded definition of Set, call it MultiSet. A MultiSet is an array where each element contains an ordered set of items.

[3 7 11]
[1 12 15]
[4 19 21]

We can calculate the global difference (call it 'cost') by the difference between the maximum 'last' value of each row and the minimum 'first' value of each row. In this case the cost will be the difference between 21 (max(11,15,21)) and 1 (min(3,1,4)), which is 20.

The process will now be to iterate the MultiSet until we reach minimum cost using the following algorithm:

• identify the row with the lowest value. If this row has only one element then continue, otherwise consider the potential cost reduction of removing the values from this row which are lower than the lowest value from any other row.
• identify the row with the highest value. If this row has only element then continue, otherwise consider the potential cost reduction of removing the values from this row which are higher than the highest value from any other row.
• remove those values identified above and continue to the next highest/lowest items. -
• If lowest and highest values are both in single-item rows then the cost has been minimised.

To demonstrates in the given example, the original cost of 20 can be reduced to 18 by removing the lowest value of 1 (the lowest value in the MultiSet which is lower than any other rows minimum), or reduced to 14 by removing the highest values of 19 and 21 (the highest values in the MultiSet which are higher than any other row's maximum, i.e. 15) from the final row. The resulting MultiSet would be

[3 7 11]
[1 12 15]
[4]

The second iteration has us remove the 12 and 15 to reduce the cost to 10.

[3 7 11]
[1]
[4]

And the third and final iteration has us remove the 7 and 11 to reduce the cost to 3. After the third iteration the global difference can no longer be minimised, thus the solution is reached.

The complexity? Upper bounded by O(n * m * log(n) * k)

Answer 4

If I understand correctly, you want to find the set in which the largest difference within its elements is globally minimal. (I will call that the range of the set)

Start with k sets, with each of them initially contain the an element from the first array. For each set, the minimum and maximum would be equal to the element itself. For your example that would be {3}, {7} and {11}.

Then you move on to the second array. For each set, you have to pick an element from that array that minimizes the new range. Ideally you would select an element that does not increase the range (but that's not possible now). If that's not possible, select the elements that expand your sets going both direction (plus and minus). For the example that would give you {1-3}, {3-12},{1-7},{7-12},{1-11} and {11-12}. From these 2k sets, you can remove sets that are overlapping. For example, the set {1-7} will always have a larger or equal range compared to the set {1-3}. You don't need to investigate the {1-7} set. You end up with sets {1-3} and {11-12}.

Moving on to the third array, again select the elements that expand the ranges of each sets as small as possible. You end up with {1-4}, {11-19} and {4-12}. Then just select the one with the lowest range.

Answer 5

Iterate over all n * k elements.

Say our current element has value v. Let's calculate the minimum difference assuming that v is the minimum value in the resulting n-tuple.

Binary search the position of v in the other n - 1 arrays (since they're sorted, we can do it), and notice that to reduce the difference it's optimal to pick the smallest elements that are greater than or equal than v for all the other arrays. This is precisely what the binary search gives us.

An example:

[3 7 11]
[1 12 15]
[4 19 21]

If we take v = 1 on the second array, then we'll pick 3 on the first array, and 4 on the second.

The complexity is O(N * K * N * log(N)) = O(N^2 * log(N) * K).