Create Min-Heap of type HeapNode.( HeapNode- Every Node will store the data and the list no from which it belongs).

Now take one element from each of the K list and create HeapNode object and insert into min-Heap.

While inserting keep track of maximum value node inserted, call it as currMax.

Extract the minimum Node from the min-Heap call it as min, calculate the range = currMax-min.

The extracted node will also contain the list to which it belongs, insert the next element from that list into min-Heap.

Keep track of the minimum range after every iteration of extracting min node and inserting new node into the heap.

If any point of time any list gets over, return the range, this will be the smallest range in K-list which contains at least one element from each list.

See the gif below for better understanding.

Shortest Range in K-sorted Lists

Complete Code:

Output:

Smallest Range is: 2 from 1 To 3

__________________________________________________ Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________