Smallest range covering all k lists

Question

You have k sorted lists of numbers. Find the smallest range [a, b] (smallest b - a, ties broken by smaller a) that contains at least one number from each of the k lists. Target O(N \log k) time for N total elements, O(k) memory.

Accepted Answer

The same heap-of-fronts machine that merges streams solves this. Walk one pointer per list forward through the merged order. At every moment you hold one "current" value from each list; the tightest range that covers all of them right now runs from the minimum of those current values to the maximum. A min-heap gives you the minimum in O(\log k), and you track the maximum separately. To shrink the window, advance the list whose value is the minimum (any other move can only keep the max as high or higher and cannot help). Record the best window each step. Stop the instant a list runs out, becau…

Smallest range covering all k lists

Your answer

More Coding questions