Smallest Range Covering Elements from K Sorted Lists

You are given k lists of integers, each individually sorted in non-decreasing order (the lists may have different lengths). Find the smallest range [lo, hi] such that at least one element from every one of the k lists falls within [lo, hi] (inclusive). A range's width is hi - lo. If several ranges share the same smallest width, output the one with the smallest lo.

Input: The first line contains the integer k. This is followed by k list-blocks, each consisting of a line with that list's length followed by a line with that many space-separated integers (sorted non-decreasing). Output: Print two space-separated integers: the lo and hi of the smallest covering range.

1 <= k <= 100 1 <= length of each list <= 1000 -10^9 <= value <= 10^9 Each list is individually sorted in non-decreasing order.

This is the SAME core heap-based technique as merging k sorted lists, extended with one additional piece of tracked state (the running maximum) to turn a pure merge into a range-minimization search - recognizing shared techniques across seemingly different problems is a valuable, transferable skill.

Find the narrowest range that includes at least one element from every one of k sorted lists. Brute force: Try every possible combination of one element from each list and compute the range for each - this is combinatorially expensive (product of all list lengths), completely impractical. Optimised: Since the heap always holds the CURRENT minimum across a synchronized 'one pointer per list' state, and the tracked maximum captures the current range's upper bound, advancing ONLY the list behind the minimum (never any other) guarantees every meaningfully different range is explored in increasing order of its start - each step considers exactly one new candidate range in O(log k), with the maximum updated incrementally rather than recomputed from scratch.

1. Maintain ONE POINTER per list, all starting at index 0, and track the MAXIMUM value among all k currently-pointed-to elements. 2. Use a MIN-HEAP keyed by the pointed-to value to repeatedly find which list currently holds the SMALLEST pointed-to value - the current candidate range is [that smallest value, the tracked maximum]. 3. Always advance the pointer belonging to whichever list held the minimum, and recompute the maximum incrementally (it can only GROW, since you're removing the current minimum, never the maximum) - stop the moment any list's pointer runs past its end.

Time: O(N log k), where N is the total number of elements across all k lists - each element is pushed and popped from the heap at most once. Space: O(k), for the heap holding one candidate per list.

k = 1 (any single element works, so the smallest range is the smallest element paired with itself, width 0); lists that share a common value, allowing a width-0 range.

Be ready to explain WHY advancing only the list behind the current MINIMUM (never any other list) is correct and sufficient - advancing any other list could only ever make the range worse or redundant, never better, a key justification interviewers often probe for.