Crack the Backend

Problem Statement

You have k sorted lists. Find a smallest range [a, b] such that each list contains at least one element in [a, b]. "Smallest" means minimize b - a; if tie, minimize a. Return [a, b].

Key Observations

Min-heap + sweep: Put the first element of each list into a min-heap (store value, listId, index). Let max = current maximum among these. The current "range" is [min from heap, max]. Pop the min, update the best range if (max - min) is smaller; then push the next element from the same list (if any) and update max. When one list is exhausted we stop (we can't have one element from each list anymore).

Approach

High-level: Heap of (val, listId, idx). Initialize with first element of each list; max = max of these. While we have k elements: pop min, update best [min, max]; push next from same list; update max. Return best range.

Steps: PriorityQueue<int[]> pq by val; int max = Integer.MIN_VALUE; for each list offer (first, listId, 0), max = Math.max(max, first). int[] best = {min, max}; while true: int[] cur = pq.poll(); update best if (max - cur[0]) smaller; if cur[2]+1 < list size push next and update max; else break. return best;

Implementation

Java

public int[] smallestRange(List<List<Integer>> nums) {
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0]-b[0]);
    int max = Integer.MIN_VALUE;

    for (int i = 0; i < nums.size(); i++) {
        pq.offer(new int[]{nums.get(i).get(0), i, 0});
        max = Math.max(max, nums.get(i).get(0));
    }

    int[] best = new int[]{pq.peek()[0], max};

    while (pq.size() == nums.size()) {
        int[] cur = pq.poll();

        if (max - cur[0] < best[1] - best[0]) {
            best = new int[]{cur[0], max};
        }

        int i = cur[1], j = cur[2] + 1;

        if (j >= nums.get(i).size()) {
            break;
        }

        int val = nums.get(i).get(j);
        pq.offer(new int[]{val, i, j});
        max = Math.max(max, val);
    }

    return best;
}

Test Cases

Example 1

Input

nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]

Expected

[20,24]

Explanation

Range [20,24] covers all lists.

Complexity Analysis

Time: typically O(n log k) or O(n log n).
Space: O(k) or O(n).

Follow-ups

Stream: process one element at a time.