# 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.

## Java

Output:

Minimum range is 4-6

The 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.     (1 votes, average: 5.00 out of 5) Loading... 