Smallest Range From K Sorted List

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
85 upvotes
Asked in companies
OlaCleartax

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 2
2 4 5
5 6 7
2 3
1 1
9 12
4 9
Sample Output 1 :
1
9
Explanation For Sample Input 1 :
Test case 1 :
The given list are [2, 4, 5], [5, 6, 7]. The range [5, 5] will include 5 which is present in both the list and hence the length of this range is 1. This is the only possible range having the minimum length.

Test case 2 :
The given list are [1, 1], [9, 12], [4, 9]. The range [1, 9] will include 1 which is present in the first list, and 9 which include in both the second and third list  The length of the range is 9 (9 - 1 + 1 = 9).
Sample Input 2 :
2
3 3
4 7 30
1 2 12
20 40 50
5 1
3 6 8 12 31
Sample Output 2 :
14
1
Explanation For Sample Input 2 :
Test case 1 :
The given list are [4, 7, 30], [1, 2, 12] and [20, 40, 50]. The range [7, 20], hence the length of this range is 14. This is the only possible range having the minimum length.

Test case 2 :
The range [3, 3] will include 3 which is present in the first list. The length of the range is 1. Infect, we can select any of element present in first list as there is only one list given to us.
Hint

Check all possible ranges and get the required one.

Approaches (3)
Brute Force Approach

Approach:

  1. To get all possible ranges we first merge all ‘K’ lists into one single list and then traverse on all possible pairs.
  2. 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).
  3. 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.
  4. 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.
Time Complexity

O(N^3 * K^3), where ‘N’ is the number of elements present in each list and ‘K’ is the number of lists. 

For each of the ‘K’ lists, we have ‘N’ elements so the total number of elements is N*K. Now for generating each possible pair of elements will take O((N * K) ^ 2) time and for each pair we need to traverse on each list in the worst case we will traverse all the elements which will take O(N * K) time. So overall time complexity in the worst case will be O((N * K)  ^3)

Space Complexity

O(N * K), where ‘N’ is the number of elements present in each list and ‘K’ is the number of lists.

We are using a list for storing all pairs. So space complexity will be O(N * K).

Code Solution
(100% EXP penalty)
Smallest Range From K Sorted List
Full screen
Console