Smallest Range Covering Elements from K Lists

Hard Heaps Merge K Sorted Original on LeetCode

Reported atArcesiumPhonePe

Smallest Range Covering Elements from K Lists is a hard heaps problem solved with the merge k sorted pattern. The best approach, optimal (min-heap of one pointer per list), runs in O(N log k) time and O(k) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from try every start value up.

Problem

You are given k lists of integers, each sorted in non-decreasing order. Find the smallest range [a, b] that contains at least one number from every list.

A range [a, b] is smaller than [c, d] when b - a < d - c, or when the widths are equal and a < c. Return the smallest range as [a, b].

Examples

Example 1

Input
nums = [[1, 8, 15], [4, 9, 20], [6, 11]]
Output
[6, 9]
Why
6 comes from the third list, 8 from the first and 9 from the second; [8, 11] is just as wide but starts later.

Example 2

Input
nums = [[5, 6], [5, 7], [5]]
Output
[5, 5]
Why
5 is in every list, so a single-point range works.

Example 3

Input
nums = [[-3, 10], [0, 12], [4, 20]]
Output
[-3, 4]
Why
Picking -3, 0 and 4 gives width 7; every other choice is wider, for example [4, 12] has width 8.

Constraints

  • 1 <= k == nums.length <= 3500
  • 1 <= nums[i].length <= 50
  • -10^5 <= nums[i][j] <= 10^5
  • Every nums[i] is sorted in non-decreasing order.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Try every start valueO(N · k · log m)O(1)
Merge, then sliding windowO(N log N)O(N + k)
Optimal (min-heap of one pointer per list)O(N log k)O(k)

1Try every start value

TimeO(N · k · log m)N candidate starts, each doing k binary searches over lists of length at most m.
SpaceO(1)Only the running best range.

The left end of an optimal range is one of the elements. For each element a as the left end, every list must contribute its smallest value that is >= a; the right end is the largest of those. Binary search finds each list's value.

  1. For every element a (in any list):
  2. For every list, binary search the first value >= a; if a list has none, a cannot be a start.
  3. b = the maximum of those values. Keep [a, b] if it is narrower, or equally narrow with a smaller a.
class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int bestA = 0, bestB = 0;
        boolean found = false;
        for (List<Integer> src : nums) {
            for (int a : src) {
                int b = a;
                boolean ok = true;
                for (List<Integer> list : nums) {
                    int lo = 0, hi = list.size();
                    while (lo < hi) {
                        int mid = (lo + hi) / 2;
                        if (list.get(mid) >= a) hi = mid; else lo = mid + 1;
                    }
                    if (lo == list.size()) { ok = false; break; }
                    b = Math.max(b, list.get(lo));
                }
                if (!ok) continue;
                if (!found || b - a < bestB - bestA || (b - a == bestB - bestA && a < bestA)) {
                    bestA = a; bestB = b; found = true;
                }
            }
        }
        return new int[] { bestA, bestB };
    }
}

2Merge, then sliding window

TimeO(N log N)Sorting all N elements; the window itself is linear.
SpaceO(N + k)The merged pair array and a counter per list.

Flatten everything into (value, list index) pairs and sort by value. Now the task is the classic minimum window that contains every list index at least once: grow the right edge, and while all k lists are covered, record the window and shrink from the left.

  1. Build pairs (value, listIndex) and sort by value.
  2. Move right over the pairs, counting how many times each list appears in the window and how many lists are covered.
  3. While covered == k: compare [pairs[left].value, pairs[right].value] with the best, then drop pairs[left] and move left forward.
class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int k = nums.size();
        List<int[]> all = new ArrayList<>();
        for (int i = 0; i < k; i++)
            for (int v : nums.get(i)) all.add(new int[] { v, i });
        all.sort((x, y) -> Integer.compare(x[0], y[0]));
        int[] count = new int[k];
        int covered = 0, left = 0;
        int bestA = 0, bestB = Integer.MAX_VALUE;
        for (int right = 0; right < all.size(); right++) {
            if (count[all.get(right)[1]]++ == 0) covered++;
            while (covered == k) {
                int a = all.get(left)[0], b = all.get(right)[0];
                if ((long) b - a < (long) bestB - bestA) { bestA = a; bestB = b; }
                if (--count[all.get(left)[1]] == 0) covered--;
                left++;
            }
        }
        return new int[] { bestA, bestB };
    }
}

3Optimal (min-heap of one pointer per list)

TimeO(N log k)Each of the N elements is pushed and popped at most once in a heap of size k.
SpaceO(k)The heap holds exactly one entry per list.

Hold one element from every list in a min-heap and track the largest of them. The heap top and that maximum form a valid range. To find a narrower one, the only useful move is to replace the minimum with the next element of its list; when some list runs out, no further range is possible.

  1. Push the first element of every list into a min-heap (value, list, index) and set curMax to the largest of them.
  2. Pop the minimum; if curMax - min is narrower than the best, record [min, curMax].
  3. If its list has a next element, push it and update curMax; otherwise stop.
class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
        int curMax = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            int v = nums.get(i).get(0);
            pq.offer(new int[] { v, i, 0 });
            curMax = Math.max(curMax, v);
        }
        int bestA = 0, bestB = Integer.MAX_VALUE;
        while (true) {
            int[] top = pq.poll();
            int min = top[0];
            if ((long) curMax - min < (long) bestB - bestA) { bestA = min; bestB = curMax; }
            List<Integer> list = nums.get(top[1]);
            int next = top[2] + 1;
            if (next == list.size()) break;
            int v = list.get(next);
            pq.offer(new int[] { v, top[1], next });
            curMax = Math.max(curMax, v);
        }
        return new int[] { bestA, bestB };
    }
}

Edge cases to test

  • A single list: the answer is its smallest element twice
  • A value present in every list gives a width-0 range
  • Two ranges with the same width: return the one with the smaller start
  • Duplicate values inside one list
  • Negative values

Hints

Hint 1

A best range can always start at some element and end at some element. If you fix the start, what is the best end?

Hint 2

Keep one pointer per list. The current range runs from the smallest pointed-to value to the largest. Which pointer is worth moving?

Hint 3

Only advancing the list that holds the current minimum can shrink the range. A min-heap of the k current values finds it quickly, and you stop when that list runs out.

FAQ

What is the best time complexity for Smallest Range Covering Elements from K Lists?

Optimal (min-heap of one pointer per list) runs in O(N log k) time and O(k) extra space. Each of the N elements is pushed and popped at most once in a heap of size k.

Which pattern does Smallest Range Covering Elements from K Lists use?

It is a heaps problem that uses the merge k sorted pattern. Other problems with the same pattern: Merge k Sorted Lists, Merge k Sorted Arrays, Design Twitter.

Is there a brute force solution for Smallest Range Covering Elements from K Lists?

Yes. Try every start value takes O(N · k · log m) time and O(1) space. The left end of an optimal range is one of the elements.

Which edge cases should I test for Smallest Range Covering Elements from K Lists?

A single list: the answer is its smallest element twice; A value present in every list gives a width-0 range; Two ranges with the same width: return the one with the smaller start; Duplicate values inside one list; Negative values.