Last Updated: 5 Jan, 2021
Smallest Range From K Sorted List
Moderate
Asked in companies
You are given ‘K’ lists containing non-negative integers. Each list has a size ‘N’ and is sorted in non-decreasing order. You need to find the minimum length of a range such that at least one element of each list must be included in that range.
For example :
If we have 3 lists as [1, 10, 11], [2, 3, 20], [5, 6, 12] then the [1, 5] is the range that includes 1 from the first list, 2,3 from the second list, and 5 from the third list i.e, this range contains at least one element from each list.
Input Format :
The first line of the input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains two space-separated positive integers ‘N’ and ‘K’ denoting the number of the elements present in each list and the number of the lists respectively.
In the next ‘K’ lines of each test case, the ith line contains ‘N’ space-separated integers denoting the elements of the ith list.
Output Format :
For every test case, print a positive integer denoting the minimum length of the range.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= 'T' <= 50
1 <= 'N' <= 10 ^ 4
1 <= 'K' <= 10 ^ 4
1 <= 'N' * 'K' <= 10 ^ 4
1 <= 'VAL' <= 10 ^ 9
Where 'VAL' is the value of any element of any list.
Time Limit: 1 sec
Approaches
Approach:
- To get all possible ranges we first merge all ‘K’ lists into one single list and then traverse on all possible pairs.
- For each pair, we assume the first element of the pair as the starting of our range and the second element as the ending of our range (vice versa if the first element is greater than the second element).
- Now we need to check whether this range can cover at least one element from each list so we traverse on each list and for each element, we check whether it is included in our current range or not.
- If we found atleast one element from each list for the current range then this range is valid so for all valid ranges we need to take the range having a minimum length.
Approach:
- We will use the condition that each list is sorted in this approach.
- Initially, we make an array of indexes where index[i] will store the index of the element in the ith list which we need to consider to include in our current range.
- We initialize all elements in index[] to 0 which means that we need to include the first element of each list in our range.
- Now to cover all these elements we need a range whose starting and ending should be the minimum and maximum element among all the elements which are present on the index ‘index[i]’ in the ith list i.e, a[i][index[i]]. Because by choosing them as starting and ending we ensure that at least one element of each list will be covered by this range.
- We got our valid range and the length will be a (maximum element - minimum element +1) but we want the length of the range to be the minimum possible. To do so, there are two options: Either decrease the maximum element or increase the minimum element.
- Now, the maximum value can't be reduced any further, since it already corresponds to the minimum value in one of the lists. Reducing it any further will lead to the exclusion of some elements.
- Thus we increase the minimum element. To do so will move forward in the list which is containing a minimum element that we found above and take the next element into consideration. ( as the list is sorted the next element will have greater value ). We increment the entry at the corresponding index in index[] to indicate that the next element in this list now needs to be considered.
- Thus, at every step, we find the maximum and minimum element being pointed currently, update the index[] appropriately, and also find out the range formed by these maximum and minimum elements to find out the smallest range satisfying the given criteria.
- While doing this process, if any of the lists gets completely exhausted, it means that the minimum value is increased for minimizing the range. Hence we will stop the process to return the smallest range recorded so far.
Approach:
- The idea and process will remain as the previous approach. The only change we will be doing in this approach is to reduce the time taken by finding the minimum and maximum element among the elements in our consideration.
- We will use a Min heap to store the elements in our consideration to get the minimum element in logarithmic time instead of linear time as in the previous approach.
- According to the previous approach initially maximum elements will be from the first elements of each list. So whenever we increase the minimum element by taking the next element according to the ‘index[i]’ we will compare its maximum element and update our maximum element accordingly.
- The rest of the algorithm will remain as the previous approach.
Similar problems