Command Palette

Search for a command to run...

Hectal
Problem 18.8 · Heaps and Priority QueuesHard

Smallest Range Covering Elements from K Lists

PatternK-Way MergeSliding Window: Variable Size

What it teaches: K-way merge with a window: the heap holds one element per list; the range is heap minimum to the running maximum.

Practise it on judges as “Smallest Range Covering Elements from K Lists”.

The problem

Given k sorted lists, return the smallest range [a, b] that includes at least one number from each list. Range [a, b] is smaller than [c, d] if b − a < d − c, or if they're equal and a < c.

Example 1

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

Constraints

  • 1 ≤ k ≤ 3500
  • Each list sorted, 1 ≤ length ≤ 50

Pattern clues in the wording

  • → One element from each of K sorted lists
  • → Minimise max − min

These clues point to K-Way Merge: Put the first element of each sorted list in a min-heap, repeatedly take the smallest, and push its successor.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        return new int[2];
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
[20,24]
2
nums = [[1,2,3],[1,2,3],[1,2,3]]
[1,1]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Heap of fronts + running max · O(N log k)
1

Heap of fronts + running max

Time O(N log k) Space O(k)

Push the first element of each list and track the max. Repeatedly: the range is heap.min to max; record it if smaller; pop the min and push the next element from its list (updating max). Stop when a list runs out.

Approach 1
import java.util.*;

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        int max = 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});
            max = Math.max(max, v);
        }
        int[] best = {pq.peek()[0], max};
        while (true) {
            int[] t = pq.poll();
            if (max - t[0] < best[1] - best[0]) best = new int[]{t[0], max};
            List<Integer> list = nums.get(t[1]);
            if (t[2] + 1 == list.size()) return best;
            int v = list.get(t[2] + 1);
            pq.offer(new int[]{v, t[1], t[2] + 1});
            max = Math.max(max, v);
        }
    }
}

Verdict: Each element is pushed once.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Lists with equal elements
  • k = 1

Mistakes people make

  • Advancing a list other than the one with the minimum (can't shrink the range).

Interview

Follow-up questions

How is this related to Minimum Window Substring?