Smallest range that includes at least one number from each of the k lists

Question

You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.

For example,

List 1: [4, 10, 13, 14] 

List 2: [0, 9, 15, 18] 

List 3: [5, 18, 22, 30] 

The smallest range here would be [14, 18] as it contains 14 from list 1, 15 from list 2, and 18 from list 3.

MY approach is:

• Just use a MinHeap and insert the first elements from K lists
• Remove the the min element and add the next element from the corresponding list
• Simultaneously track the max and min value so that we can calculate the minimum range

But the only issue I am facing is: Suppose for one list there is no more elements left than should I finish there or should I continue?

Answer 1

Very nice O(n log n) algorithm!

You can finish there because you will never find the better interval fulfilling the given condition "range that includes at least one number from each of the k lists".

Suppose you are leaving current minimum m (the last element from some list) and instead you are removing something (not minimum) from another list. In that case the range can only grow (because minimum of the range is determined by m). So there is no point in doing that and you can just stop your algorithm.