Find smallest range with at-least one element from each of the given lists

Given M sorted lists of variable length, efficiently compute the smallest range that includes at-least one element from each list.

 

For example,

Input: 4 sorted lists of variable length

[ 3, 6, 8, 10, 15 ]
[ 1, 5, 12 ]
[ 4, 8, 15, 16 ]
[ 2, 6 ]

Output:

Minimum range is 4-6

 

Input: 4 sorted lists of variable length

[ 2, 3, 4, 8, 10, 15 ]
[ 1, 5, 12 ]
[ 7, 8, 15, 16 ]
[ 3, 6 ]

Output:

Minimum range is 4-7

 


 

We can solve this problem in O(N * logM) time where N is total number of element present in all lists by using a min-heap. The idea is to construct a min-heap of size M and insert first element of each list into it. Then we pop root element (minimum element) from the heap and insert next element from “same” list as popped element. We repeat this process until any list is exhausted. To find the minimum range, we maintain a variable high that stores the maximum element present in the heap at any point. We know that the minimum element is present in the min-heap at its root. So, at every pop operation, we compute the range (high element – root element) and return the minimum range found.

 
C++ implementation –
 

Download   Run Code

Output:

Minimum range is 4-6

 

Time complexity of above solution is O(N * logM) as heap has size M and we pop and push at-most N times where N is the total number of elements present in all lists. Note that each pop/push operation takes O(logM) time.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂