Smallest range in K Lists

The problem, simply

You get k lists of numbers, each sorted from small to big. Find the smallest range [a, b] that holds at least one number from every list. Smaller means b - a is smaller. If two ranges have the same width, the one that starts lower wins. N is the count of all numbers, and n is the length of one list.

For [[1, 5, 8], [4, 12], [7, 8, 10]] the answer is [4, 7]: it holds 5 from the first list, 4 from the second and 7 from the third.

A story to remember it

Picture it

Examples

Way 1: the simple way

The best range starts at one of the numbers. So try every number x as the left end. For each list, find its smallest number that is at least x with binary search. The right end must reach the biggest of those.

1. For every number x in every list:
2. For every list, binary search the first number >= x. If a list has none, x cannot be a left end.
3. The right end is the biggest of those numbers. Keep the narrowest range, with lower start on ties.

import java.util.List;

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        long bestWidth = Long.MAX_VALUE;
        int bestLo = 0, bestHi = 0;
        for (List<Integer> list : nums) {
            for (int x : list) {                       // try x as the left end
                int hi = x;
                boolean ok = true;
                for (List<Integer> other : nums) {
                    int j = firstAtLeast(other, x);
                    if (j == other.size()) { ok = false; break; }
                    hi = Math.max(hi, other.get(j));
                }
                long width = (long) hi - x;
                if (ok && (width < bestWidth || (width == bestWidth && x < bestLo))) {
                    bestWidth = width; bestLo = x; bestHi = hi;
                }
            }
        }
        return new int[] { bestLo, bestHi };
    }

    private int firstAtLeast(List<Integer> list, int x) {   // binary search
        int lo = 0, hi = list.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (list.get(mid) < x) lo = mid + 1; else hi = mid;
        }
        return lo;
    }
}

How long it takes: N left ends, each doing k binary searches, O(N * k log n). Extra room: O(1).

Way 2: the clever way

Walk through all lists together, like merging them, and keep exactly one number from each list in a min heap. Also remember the biggest number in the heap.

1. Put the first number of each list in the heap. Set max to the biggest of them.
2. Repeat:
   • The heap top is the smallest. The range [top, max] covers every list. Keep it if it is the best so far.
   • Poll the top. If its list has no next number, stop.
   • Offer that list's next number, and raise max if needed.

Why move only the smallest? Every range must cover the current smallest's list. Keeping the smallest and moving any other number can only push max up, so the range can not get better that way.

import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        // {value, which list, position in that list}
        PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            int v = nums.get(i).get(0);
            heap.offer(new int[] { v, i, 0 });
            max = Math.max(max, v);
        }

        int bestLo = 0, bestHi = 0;
        long bestWidth = Long.MAX_VALUE;
        while (true) {
            int[] top = heap.poll();                       // the smallest of the group
            long width = (long) max - top[0];
            if (width < bestWidth) {                       // equal width: keep the lower start
                bestWidth = width; bestLo = top[0]; bestHi = max;
            }
            int list = top[1], next = top[2] + 1;
            if (next == nums.get(list).size()) break;      // this list ran out
            int v = nums.get(list).get(next);
            heap.offer(new int[] { v, list, next });
            max = Math.max(max, v);
        }
        return new int[] { bestLo, bestHi };
    }
}

How long it takes: every number enters and leaves the heap at most once, and the heap holds k entries, so O(N log k). Extra room: the heap, O(k).

Watch out for

• Keep max as a separate variable. A min heap cannot tell you its biggest item quickly.
• Use long for widths. max - min can overflow when numbers are near the int limits.
• On a tie in width, keep the range with the lower start. Since the smallest only goes up, updating only on strictly smaller width does that.
• Read numbers with get(i) on List<Integer>. Comparing two Integer objects with == compares boxes, not values.

What interviewers ask next

• Another way without a heap? Merge all numbers into one list tagged with their list number, sort it, then slide a window that keeps a count per list. Shrink from the left while all k lists are still covered. That is O(N log N).
• Smallest range covering all elements of a pattern in one array? That is the minimum window substring idea, with a sliding window and counts.
• Why is moving the smallest always safe? The range must include something from the smallest's list. Any range that keeps the current smallest and changes something else is at least as wide, so we lose nothing by moving on.
• Same problem but the lists are huge files? Stream each file in order. The heap only ever needs one number per file in memory.

Remember this

Grown-up words: the classes are sorted lists, the group is a min heap of size k (a k-way merge), the tallest pick is the running maximum, and the gap between shortest and tallest is the range width.