Minimum Range over K arrays

Introduction

This is one interesting problem with a non-trivial solution, this has been asked in couple of good interviews. Here goes the problem statement.

“Given K positive integer arrays, each of which contains elements in sorted order. Find a range of integers such that it must contain at least one element from each array and the range is minimum.”

May be a diagram can make this more clear. Here you go!

Understanding the Minimum Range over K arrays problem.

In the above diagram we have 3 arrays each containing elements in increasing order. Now, let us identify a range which contains at least one element from each array. Clearly we can choose the range 0 – 100 and then we can get our desired result of having at least one element from each of the array in our range.

What is wrong with this range?
This range is too big!!. We can probably do better, let’s see.
Can we have a range 0 – 20 ?
Yes of course that is another range which satisfies the first condition and it is much smaller than 0 – 100.

I think, the problem statement is clear now. We now understand that we can have infinite ranges which can satisfy the first condition. But it will be a very small subset of ranges which satisfies the second condition.

In case there are multiple such ranges, we are mostly interested in the first such range.

The Idea behind this solution

Do not even think of solving in a brute force way. In case you are tempted to do so, just think how many possibilities you need to evaluate if there are three arrays and each of them have around 5 elements. You might end up evaluating 5 * 5 * 5 i.e.125 possible sets of numbers to identify the smallest range.

Now, think over having 10 arrays with 100 elements each. I really don’t want to count this, very soon you will end up hanging the system or it may go out of memory.

A better approach

Let us re-evaluate the problem. What exactly we know about it?
We know the following facts:

• The numbers in each of the array are sorted
• We want to find a range(min and max value) which contains at least one number from each array
• We need to minimize the range

Given these information, we can start looking at the first number in each array. Identify the min and max value over these elements. The ranges can be calculated as max – min.

Now, we have one range for reference and one set of elements which satisfy the first condition. The task is very simple here on wards.

Let us say that the ith array has the smallest first element, so how can we shrink the range further. We can look at the second element in the ith array as this element is greater than the first element, now the range has to shrink because we added a larger element into the range and the difference `max - min' < max - min`, irrespective of the array in which the `min'` lies.

Let us understand using a diagram and for simplicity we can use three arrays as below:

Just for the sake of understanding it visually, we will have one pointer for each array. Position the pointers at the first element of each array.

Step 1 Now consider the elements pointed by the respective pointers and calculate the range. The minimum of the three elements is 2. The range would be (2 to 8) and hence the magnitude of the range is 8-2 = 6.

Step 2 Now move the pointer of the third array one step to the right(basically we are removing the smallest element responsible for increasing the range and adding up another element from the same array which will shrink the range).

Calculate the range from the elements which are pointed by the pointers now. The minimum of the three elements is 3 an the range would be (3 to 8) and the magnitude is 8-3 = 5. Which is lesser than our previous magnitude, so we are moving towards a better and shorter range.

That’s the idea!!

Step 3 move the pointer in the third array one step to the right. Now the minimum of the three elements is 5 and it lies in the first array. Hence the range converges to (5 to 8) and the magnitude is 8-5 = 3. This is much better than the previous range.

Step 4 move the pointer in the first array one step to the right. Now the minimum among the three elements is 6 and it lies in the third array. Now the range is (6 to 9) and the magnitude is 9-6 = 3. Notice that we have a new maximum now which is 9, this happened as a result of moving the array in the first pointer.

Step 5 move the pointer in the third array one step to the right. Now the minimum of the three elements is 7 and the range becomes (7 to 9), which makes the magnitude of the range 9-7 = 2. And that is great!

Now move the pointer of the third array to the right. Oh! we exhausted the array, now we cannot move further.

What does that mean?
This means that now even if we move in any other array, we are not going to shrink the range because any movement to the right will increase the max value which is currently 9.

So, ideally we got our solution and that is the range 7 to 9.
Here is an animation for the same:

There was one flaw though, which we shamelessly overlooked. There might be a possibility that we move to the right and the range starts growing in stead of shrinking. So, in that case we must maintain the shortest magnitude in a variable an the two values responsible for this magnitude.

If by any chance, we happen to increase the range, then after breaking out of our iteration, we can always go and look at our magnitude variable an decide upon the correct result.

Analysis

Running Time of the algorithm would vary depending on the data structure we are using for extracting the min of the K elements in each iteration. We can actually use a Min Priority Queue which gives a Min in O(1) time. Of course it will take O(logN) time if implemented using a Min Heap, O(N) time if implemented using an Array or Linked List.

The outer loop actually runs till we exhaust one of the arrays. The inner loop runs K times for each iteration of the outer loop. So, in worst case we will need to traverse each of the array completely. Which means if the total number of elements are N per array, then the worst case running time would be O(KNlogK) where K is the number of arrays, N is the numbers per array and logK is the extractMin operation.

Auxiliary Space We use an array for storing the latest index of each array which is O(K) space and also, we use a priority queue of size K to store the elements pointed by the current pointers which is again O(K). Hence the asymptotic time would be O(K)

Conclusion

This problem gives a good insight of how priority queues are useful. Also, I feel this problem has a slight resemblance to the dutch flag problem not sure though.

You can improve a bit on the running time and space but that makes the solution more complex and manipulation of lot of variables without significant gain in the running time. This seems to be an optimal working solution.

Don’t forget to subscribe to TechieMe to get updates on latest posts.