277. Smallest Range Covering Elements From K Lists

You are given k lists of integers, each already sorted in ascending order. Find the smallest range [start, end] (start <= end) such that it contains at least one number from every list. If several ranges tie for the smallest length, print the one with the smallest start. Print start and end, space-separated.

Input: The first line contains an integer k, the number of lists. For each of the k lists, one line gives its length, followed by a line of that many space-separated ascending integers. Output: Print two integers, space-separated - the start and end of the smallest range covering at least one element from every list.

1 <= k <= 100, 1 <= each list's length <= 1000

This builds directly on the 'merge k sorted lists' heap technique, adding just one extra piece of tracked state (the current maximum) to turn a pure merge into a range-minimization search.

Given k sorted lists, find the smallest range that includes at least one number from every single list. Brute force: Try every possible combination of one element from each list directly, computing the range for each combination - 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 you explore every meaningfully different range in increasing order of their start - each step considers exactly one new candidate range in O(log k).

Merge all elements from all k lists into one array of (value, sourceListIndex) pairs and sort it by value. Then slide a window across this sorted array with two pointers, using a count array of size k to track how many elements from each list currently fall inside the window and a counter of how many distinct lists are represented; expand the right edge until all k lists are covered, then shrink from the left while coverage holds, recording the range whenever it improves on the best found. This is the classic minimum-window-covering-all-groups pattern, driven by one sort and one linear sweep. Time: O(n log n) Space: O(n)

For every element from any list, treat it as a candidate range start and scan forward through a merged view of all elements to find the smallest end such that every one of the k lists has contributed at least one value within that range, keeping the best (smallest, then smallest-start) range found over all candidate starts. This is correct because it directly checks the definition of a covering range, but repeating a full scan-and-coverage-check for every candidate start multiplies the work. Time: O(n^2 * k) Space: O(n)

Keep one pointer per list in a min-heap (initialized to each list's first element) along with a running maximum of the values currently pointed to. Repeatedly pop the minimum, compare (currentMax - poppedMin) to the best range found so far, then advance that list's pointer and push its next value (updating the running maximum if needed); stop as soon as any list runs out, since a valid range must include every list. Because the heap only ever holds k elements instead of sorting all n, this scales much better when the number of lists k is far smaller than the total element count n. Time: O(n log k) Space: O(k)

1. Seed a min-heap with the current value from every list (starting at each list's first element), tracking the maximum value currently represented alongside it. 2. At each step, the gap between the heap's current minimum and the tracked maximum is a valid candidate range - compare it to the best range found so far. 3. Advance ONLY the list that contributed the current minimum (pop it, push its next element, update the tracked maximum) - stop the moment any list runs completely out of elements.

Time: O(N log k), where N is the total number of elements across all 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 (the range collapses to a single element from that one list), lists of very different lengths, and k up to 100 with each list up to 1000 elements for heap performance.

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.