#87 · Heap / Priority Queue

Smallest Range Covering Elements from K Lists

Given k lists of integers sorted in non-decreasing order, find the smallest range [a, b] that includes at least one number from each of the k lists. Among equally small ranges, prefer the one with the smaller start.

HardLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Min-heap of one current element per list

The heap always contains exactly one value from each list. Its top is the minimum (the left end of the current window) and a separately tracked maximum is the right end. Popping the minimum and pushing the next value from the same list slides the window forward.

Memory layout

A contiguous array of k entries; children of i at 2i + 1 and 2i + 2.

Operation	Cost
push / pop	O(log k)
peek	O(1)

Sliding window over a merged, tagged list

Merge all values into one sorted list of (value, list id). The answer is the shortest window containing every list id at least once, found with the classic two-pointer count technique.

Memory layout

An array of N pairs plus k counters.

Operation	Cost
sort	O(N log N)
window	O(N)

Why it fits

A valid range must contain one value per list, and its minimum must be the smallest of those chosen values. Moving the minimum forward is the only way to make a better range, which is a job for a min-heap.
Because every list is sorted, advancing the list that supplied the minimum is always safe: smaller values in that list can only produce wider ranges.
The heap keeps k elements instead of all N, so memory is O(k) rather than O(N).

Why alternatives degrade

Merge into one sorted array only:: Sorting alone does not find the window; you still need counting for coverage (and O(N) memory).
k pointers with a linear scan for the min:: Works in O(N · k); fine for tiny k, but the heap makes each step O(log k).
Binary search on the range width:: Possible with a feasibility check, but needs the value range and re-scans lists on every probe.

Four approaches, from naive to production

1 · beginner

Try each value as the left end

time O(N · k · L)space O(1)

For every value lo in any list, take the smallest value ≥ lo from each list; the largest of those is hi. Keep the narrowest [lo, hi].

vector<int> smallestRange(vector<vector<int>>& nums) {
    long long bestLo = INT_MIN, bestHi = INT_MAX;
    for (auto& list : nums) {
        for (int lo : list) {
            long long hi = lo;
            bool ok = true;
            for (auto& other : nums) {
                auto it = lower_bound(other.begin(), other.end(), lo);
                if (it == other.end()) { ok = false; break; }
                hi = max(hi, (long long)*it);
            }
            if (ok && (hi - lo < bestHi - bestLo || (hi - lo == bestHi - bestLo && lo < bestLo))) { bestLo = lo; bestHi = hi; }
        }
    }
    return {(int)bestLo, (int)bestHi};
}

public int[] smallestRange(List<List<Integer>> nums) {
    long bestLo = Integer.MIN_VALUE, bestHi = Integer.MAX_VALUE;
    for (List<Integer> list : nums) {
        for (int lo : list) {
            long hi = lo;
            boolean ok = true;
            for (List<Integer> other : nums) {
                Integer pick = null;
                for (int v : other) if (v >= lo) { pick = v; break; }
                if (pick == null) { ok = false; break; }
                hi = Math.max(hi, pick);
            }
            if (ok && (hi - lo < bestHi - bestLo || (hi - lo == bestHi - bestLo && lo < bestLo))) { bestLo = lo; bestHi = hi; }
        }
    }
    return new int[]{(int) bestLo, (int) bestHi};
}

def smallest_range(nums):
    best_lo, best_hi = float('-inf'), float('inf')
    for lst in nums:
        for lo in lst:
            hi = lo
            ok = True
            for other in nums:
                pick = next((v for v in other if v >= lo), None)
                if pick is None:
                    ok = False; break
                hi = max(hi, pick)
            if ok and (hi - lo < best_hi - best_lo or (hi - lo == best_hi - best_lo and lo < best_lo)): best_lo, best_hi = lo, hi
    return [best_lo, best_hi]

function smallestRange(nums: number[][]): number[] {
  let best = [-Infinity, Infinity];
  for (const list of nums) {
    for (const lo of list) {
      let hi = lo;
      let ok = true;
      for (const other of nums) {
        const pick = other.find((v) => v >= lo);
        if (pick === undefined) { ok = false; break; }
        hi = Math.max(hi, pick);
      }
      if (ok && (hi - lo < best[1] - best[0] || (hi - lo === best[1] - best[0] && lo < best[0]))) best = [lo, hi];
    }
  }
  return best;
}

Flaws & bottlenecks

For each of N candidates it scans all k lists (and each find is linear).
Repeats work between neighbouring candidates.
Slow once the lists hold thousands of values.

Interviewer cross-questions

Why can the left end be restricted to input values?

Say: If the left end is not a value, raising it to the next value keeps the range valid and makes it narrower.

How do you speed up the find in each list?

Say: Binary search each sorted list, or keep a pointer per list that only moves forward as lo increases.

What does a moving pointer per list lead to?

Say: The heap solution: one current value per list, always advancing the list that holds the smallest value.

2 · intermediate

Merge everything, slide a window

time O(N log N)space O(N)

Tag each value with its list id and sort all N pairs. Slide a window with two pointers and a count per list; whenever all k lists are covered, record the width and shrink from the left.

vector<int> smallestRange(vector<vector<int>>& nums) {
    vector<pair<int, int>> items;
    for (int id = 0; id < (int)nums.size(); id++) for (int v : nums[id]) items.push_back({v, id});
    sort(items.begin(), items.end());
    int need = nums.size();
    vector<int> count(need, 0);
    int covered = 0, left = 0;
    long long bestLo = INT_MIN, bestHi = INT_MAX;
    for (int right = 0; right < (int)items.size(); right++) {
        if (count[items[right].second]++ == 0) covered++;
        while (covered == need) {
            if (items[right].first - items[left].first < bestHi - bestLo) { bestLo = items[left].first; bestHi = items[right].first; }
            if (--count[items[left].second] == 0) covered--;
            left++;
        }
    }
    return {(int)bestLo, (int)bestHi};
}

public int[] smallestRange(List<List<Integer>> nums) {
    List<int[]> items = new ArrayList<>();
    for (int id = 0; id < nums.size(); id++) for (int v : nums.get(id)) items.add(new int[]{v, id});
    items.sort((a, b) -> Integer.compare(a[0], b[0]));
    int need = nums.size();
    int[] count = new int[need];
    int covered = 0, left = 0;
    long bestLo = Integer.MIN_VALUE, bestHi = Integer.MAX_VALUE;
    for (int right = 0; right < items.size(); right++) {
        if (count[items.get(right)[1]]++ == 0) covered++;
        while (covered == need) {
            if (items.get(right)[0] - items.get(left)[0] < bestHi - bestLo) { bestLo = items.get(left)[0]; bestHi = items.get(right)[0]; }
            if (--count[items.get(left)[1]] == 0) covered--;
            left++;
        }
    }
    return new int[]{(int) bestLo, (int) bestHi};
}

def smallest_range(nums):
    items = sorted((v, i) for i, lst in enumerate(nums) for v in lst)
    need = len(nums)
    count = [0] * need
    covered = left = 0
    best_lo, best_hi = float('-inf'), float('inf')
    for right in range(len(items)):
        count[items[right][1]] += 1
        if count[items[right][1]] == 1: covered += 1
        while covered == need:
            if items[right][0] - items[left][0] < best_hi - best_lo: best_lo, best_hi = items[left][0], items[right][0]
            count[items[left][1]] -= 1
            if count[items[left][1]] == 0: covered -= 1
            left += 1
    return [best_lo, best_hi]

function smallestRange(nums: number[][]): number[] {
  const items: [number, number][] = [];
  nums.forEach((list, id) => list.forEach((v) => items.push([v, id])));
  items.sort((a, b) => a[0] - b[0]);
  const need = nums.length;
  const count = new Array<number>(need).fill(0);
  let covered = 0, left = 0;
  let best = [-Infinity, Infinity];
  for (let right = 0; right < items.length; right++) {
    if (count[items[right][1]]++ === 0) covered++;
    while (covered === need) {
      if (items[right][0] - items[left][0] < best[1] - best[0]) best = [items[left][0], items[right][0]];
      if (--count[items[left][1]] === 0) covered--;
      left++;
    }
  }
  return best;
}

Flaws & bottlenecks

Sorting ignores that the input lists are already sorted.
O(N) memory for the merged items.
The shrink loop needs careful coverage bookkeeping.

Interviewer cross-questions

How is this like "minimum window substring"?

Say: Same technique: grow right until all required kinds are covered, then shrink left while they stay covered.

Can you avoid the full sort?

Say: Yes: a k-way merge with a heap produces the sorted order lazily, which is the heap solution.

What decides ties?

Say: Shrinking only updates on a strictly smaller width, so the first (smallest-start) range of that width is kept.

3 · advanced

Min-heap of one element per list

time O(N log k)space O(k)

Push the first element of every list and track the maximum. Repeatedly pop the minimum, record [min, max] if narrower, and push the next element of the popped list; stop when a list runs out.

vector<int> smallestRange(vector<vector<int>>& nums) {
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> heap; // {value, list, index}
    long long mx = INT_MIN;
    for (int id = 0; id < (int)nums.size(); id++) {
        heap.push({nums[id][0], id, 0});
        mx = max(mx, (long long)nums[id][0]);
    }
    long long bestLo = INT_MIN, bestHi = INT_MAX;
    for (;;) {
        auto [value, id, idx] = heap.top(); heap.pop();
        if (mx - value < bestHi - bestLo) { bestLo = value; bestHi = mx; }
        if (idx + 1 == (int)nums[id].size()) break;
        int next = nums[id][idx + 1];
        heap.push({next, id, idx + 1});
        mx = max(mx, (long long)next);
    }
    return {(int)bestLo, (int)bestHi};
}

public int[] smallestRange(List<List<Integer>> nums) {
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); // {value, list, index}
    long max = Integer.MIN_VALUE;
    for (int id = 0; id < nums.size(); id++) {
        heap.add(new int[]{nums.get(id).get(0), id, 0});
        max = Math.max(max, nums.get(id).get(0));
    }
    long bestLo = Integer.MIN_VALUE, bestHi = Integer.MAX_VALUE;
    while (true) {
        int[] top = heap.poll();
        int value = top[0], id = top[1], idx = top[2];
        if (max - value < bestHi - bestLo) { bestLo = value; bestHi = max; }
        if (idx + 1 == nums.get(id).size()) break;
        int next = nums.get(id).get(idx + 1);
        heap.add(new int[]{next, id, idx + 1});
        max = Math.max(max, next);
    }
    return new int[]{(int) bestLo, (int) bestHi};
}

def smallest_range(nums):
    heap = []  # (value, list, index)
    mx = float('-inf')
    for i, lst in enumerate(nums):
        heapq.heappush(heap, (lst[0], i, 0))
        mx = max(mx, lst[0])
    best_lo, best_hi = float('-inf'), float('inf')
    while True:
        value, i, idx = heapq.heappop(heap)
        if mx - value < best_hi - best_lo: best_lo, best_hi = value, mx
        if idx + 1 == len(nums[i]): break
        nxt = nums[i][idx + 1]
        heapq.heappush(heap, (nxt, i, idx + 1))
        mx = max(mx, nxt)
    return [best_lo, best_hi]

function smallestRange(nums: number[][]): number[] {
  const heap = new Heap<number[]>((a, b) => a[0] < b[0]);
  let max = -Infinity;
  nums.forEach((list, id) => {
    heap.push([list[0], id, 0]);
    max = Math.max(max, list[0]);
  });
  let best = [-Infinity, Infinity];
  for (;;) {
    const [value, id, idx] = heap.pop();
    if (max - value < best[1] - best[0]) best = [value, max];
    if (idx + 1 === nums[id].length) break;
    const next = nums[id][idx + 1];
    heap.push([next, id, idx + 1]);
    max = Math.max(max, next);
  }
  return best;
}

class Heap<T> {
  private a: T[] = [];
  constructor(private before: (x: T, y: T) => boolean) {}
  get size() { return this.a.length; }
  peek(): T { return this.a[0]; }
  push(v: T) {
    const a = this.a;
    a.push(v);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.before(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop(): T {
    const a = this.a;
    const top = a[0];
    const last = a.pop()!;
    if (a.length) {
      a[0] = last;
      let i = 0;
      for (;;) {
        let m = i;
        const l = 2 * i + 1, r = l + 1;
        if (l < a.length && this.before(a[l], a[m])) m = l;
        if (r < a.length && this.before(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

Flaws & bottlenecks

Heap entries are small arrays (value, list, index): allocation per push.
Stopping when any list is exhausted must be explained clearly.
The maximum is tracked outside the heap and must be updated on every push.

Interviewer cross-questions

Why stop when a list is exhausted?

Say: The popped value was the minimum and has no successor in its list, so every later window would have to skip that list entirely.

Why is advancing only the popped list safe?

Say: The popped value is the window minimum. Keeping it can never narrow the range further, since the max is already fixed, so the only way to improve is to replace it with a larger value from its own list.

What is the complexity if k is 2 or 3?

Say: O(N) effectively; log k is a tiny constant. For huge k the heap matters most.

4 · expert

Index heap with guards

time O(N log k)space O(k)

Keep a pos[] array of per-list positions and a heap of list ids ordered by their current value (ties by id). No tuples are allocated. Guard empty input before touching nums[id][0].

vector<int> smallestRange(vector<vector<int>>& nums) {
    int k = nums.size();
    if (k == 0) return {};
    for (auto& list : nums) if (list.empty()) return {};
    vector<int> pos(k, 0);
    auto later = [&](int a, int b) {
        int va = nums[a][pos[a]], vb = nums[b][pos[b]];
        return va != vb ? va > vb : a > b;
    };
    priority_queue<int, vector<int>, decltype(later)> heap(later);
    long long mx = INT_MIN;
    for (int id = 0; id < k; id++) {
        heap.push(id);
        mx = max(mx, (long long)nums[id][0]);
    }
    long long bestLo = nums[heap.top()][0], bestHi = mx;
    for (;;) {
        int id = heap.top(); heap.pop();
        long long value = nums[id][pos[id]];
        if (mx - value < bestHi - bestLo) { bestLo = value; bestHi = mx; }
        if (++pos[id] == (int)nums[id].size()) break;
        heap.push(id);
        mx = max(mx, (long long)nums[id][pos[id]]);
    }
    return {(int)bestLo, (int)bestHi};
}

public int[] smallestRange(List<List<Integer>> nums) {
    int k = nums.size();
    if (k == 0) return new int[0];
    for (List<Integer> list : nums) if (list.isEmpty()) return new int[0];
    int[] pos = new int[k];
    PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> {
        int va = nums.get(a).get(pos[a]), vb = nums.get(b).get(pos[b]);
        return va != vb ? Integer.compare(va, vb) : Integer.compare(a, b);
    });
    long max = Integer.MIN_VALUE;
    for (int id = 0; id < k; id++) {
        heap.add(id);
        max = Math.max(max, nums.get(id).get(0));
    }
    long bestLo = nums.get(heap.peek()).get(0), bestHi = max;
    while (true) {
        int id = heap.poll();
        long value = nums.get(id).get(pos[id]);
        if (max - value < bestHi - bestLo) { bestLo = value; bestHi = max; }
        if (++pos[id] == nums.get(id).size()) break;
        heap.add(id);
        max = Math.max(max, nums.get(id).get(pos[id]));
    }
    return new int[]{(int) bestLo, (int) bestHi};
}

def smallest_range(nums):
    k = len(nums)
    if k == 0 or any(len(lst) == 0 for lst in nums): return []
    pos = [0] * k
    heap = []  # (current value, list id)
    mx = float('-inf')
    for i in range(k):
        heapq.heappush(heap, (nums[i][0], i))
        mx = max(mx, nums[i][0])
    best_lo, best_hi = heap[0][0], mx
    while True:
        _, i = heapq.heappop(heap)
        value = nums[i][pos[i]]
        if mx - value < best_hi - best_lo: best_lo, best_hi = value, mx
        pos[i] += 1
        if pos[i] == len(nums[i]): break
        heapq.heappush(heap, (nums[i][pos[i]], i))
        mx = max(mx, nums[i][pos[i]])
    return [best_lo, best_hi]

function smallestRange(nums: number[][]): number[] {
  const k = nums.length;
  if (k === 0 || nums.some((list) => list.length === 0)) return [];
  const pos = new Array<number>(k).fill(0);
  const heap = new Heap<number>((a, b) => nums[a][pos[a]] < nums[b][pos[b]] || (nums[a][pos[a]] === nums[b][pos[b]] && a < b));
  let max = -Infinity;
  for (let id = 0; id < k; id++) {
    heap.push(id);
    max = Math.max(max, nums[id][0]);
  }
  let bestLo = nums[heap.peek()][0], bestHi = max;
  for (;;) {
    const id = heap.pop();
    const value = nums[id][pos[id]];
    if (max - value < bestHi - bestLo) { bestLo = value; bestHi = max; }
    if (++pos[id] === nums[id].length) break;
    heap.push(id);
    max = Math.max(max, nums[id][pos[id]]);
  }
  return [bestLo, bestHi];
}

class Heap<T> {
  private a: T[] = [];
  constructor(private before: (x: T, y: T) => boolean) {}
  get size() { return this.a.length; }
  peek(): T { return this.a[0]; }
  push(v: T) {
    const a = this.a;
    a.push(v);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.before(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop(): T {
    const a = this.a;
    const top = a[0];
    const last = a.pop()!;
    if (a.length) {
      a[0] = last;
      let i = 0;
      for (;;) {
        let m = i;
        const l = 2 * i + 1, r = l + 1;
        if (l < a.length && this.before(a[l], a[m])) m = l;
        if (r < a.length && this.before(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

Flaws & bottlenecks

The comparator reads mutable state (pos), so pos[id] must change only while id is outside the heap.
More moving parts: pos array, comparator, tie-breaking.
A heap of ids is slower for tiny k than a linear scan over k pointers.

Interviewer cross-questions

Why must pos[id] change only after popping?

Say: The heap order depends on nums[id][pos[id]]. Changing it while the id is inside would silently break the heap invariant.

What are the edge cases?

Say: No lists, an empty list (no valid range), k = 1 (the smallest element as a range of width 0), duplicates across lists, negative values.

How would you reduce allocation further?

Say: Preallocate the heap array of size k and store ids in an int array; this version already avoids per-element objects.

Synchronized code walkthrough

Showing: Try each value as the left end — shares the player above; click any step to jump.

vector<int> smallestRange(vector<vector<int>>& nums) {
    long long bestLo = INT_MIN, bestHi = INT_MAX;
    for (auto& list : nums) {
        for (int lo : list) {
            long long hi = lo;
            bool ok = true;
            for (auto& other : nums) {
                auto it = lower_bound(other.begin(), other.end(), lo);
                if (it == other.end()) { ok = false; break; }
                hi = max(hi, (long long)*it);
            }
            if (ok && (hi - lo < bestHi - bestLo || (hi - lo == bestHi - bestLo && lo < bestLo))) { bestLo = lo; bestHi = hi; }
        }
    }
    return {(int)bestLo, (int)bestHi};
}

public int[] smallestRange(List<List<Integer>> nums) {
    long bestLo = Integer.MIN_VALUE, bestHi = Integer.MAX_VALUE;
    for (List<Integer> list : nums) {
        for (int lo : list) {
            long hi = lo;
            boolean ok = true;
            for (List<Integer> other : nums) {
                Integer pick = null;
                for (int v : other) if (v >= lo) { pick = v; break; }
                if (pick == null) { ok = false; break; }
                hi = Math.max(hi, pick);
            }
            if (ok && (hi - lo < bestHi - bestLo || (hi - lo == bestHi - bestLo && lo < bestLo))) { bestLo = lo; bestHi = hi; }
        }
    }
    return new int[]{(int) bestLo, (int) bestHi};
}

def smallest_range(nums):
    best_lo, best_hi = float('-inf'), float('inf')
    for lst in nums:
        for lo in lst:
            hi = lo
            ok = True
            for other in nums:
                pick = next((v for v in other if v >= lo), None)
                if pick is None:
                    ok = False; break
                hi = max(hi, pick)
            if ok and (hi - lo < best_hi - best_lo or (hi - lo == best_hi - best_lo and lo < best_lo)): best_lo, best_hi = lo, hi
    return [best_lo, best_hi]

function smallestRange(nums: number[][]): number[] {
  let best = [-Infinity, Infinity];
  for (const list of nums) {
    for (const lo of list) {
      let hi = lo;
      let ok = true;
      for (const other of nums) {
        const pick = other.find((v) => v >= lo);
        if (pick === undefined) { ok = false; break; }
        hi = Math.max(hi, pick);
      }
      if (ok && (hi - lo < best[1] - best[0] || (hi - lo === best[1] - best[0] && lo < best[0]))) best = [lo, hi];
    }
  }
  return best;
}

vector<int> smallestRange(vector<vector<int>>& nums) {
    vector<pair<int, int>> items;
    for (int id = 0; id < (int)nums.size(); id++) for (int v : nums[id]) items.push_back({v, id});
    sort(items.begin(), items.end());
    int need = nums.size();
    vector<int> count(need, 0);
    int covered = 0, left = 0;
    long long bestLo = INT_MIN, bestHi = INT_MAX;
    for (int right = 0; right < (int)items.size(); right++) {
        if (count[items[right].second]++ == 0) covered++;
        while (covered == need) {
            if (items[right].first - items[left].first < bestHi - bestLo) { bestLo = items[left].first; bestHi = items[right].first; }
            if (--count[items[left].second] == 0) covered--;
            left++;
        }
    }
    return {(int)bestLo, (int)bestHi};
}

public int[] smallestRange(List<List<Integer>> nums) {
    List<int[]> items = new ArrayList<>();
    for (int id = 0; id < nums.size(); id++) for (int v : nums.get(id)) items.add(new int[]{v, id});
    items.sort((a, b) -> Integer.compare(a[0], b[0]));
    int need = nums.size();
    int[] count = new int[need];
    int covered = 0, left = 0;
    long bestLo = Integer.MIN_VALUE, bestHi = Integer.MAX_VALUE;
    for (int right = 0; right < items.size(); right++) {
        if (count[items.get(right)[1]]++ == 0) covered++;
        while (covered == need) {
            if (items.get(right)[0] - items.get(left)[0] < bestHi - bestLo) { bestLo = items.get(left)[0]; bestHi = items.get(right)[0]; }
            if (--count[items.get(left)[1]] == 0) covered--;
            left++;
        }
    }
    return new int[]{(int) bestLo, (int) bestHi};
}

def smallest_range(nums):
    items = sorted((v, i) for i, lst in enumerate(nums) for v in lst)
    need = len(nums)
    count = [0] * need
    covered = left = 0
    best_lo, best_hi = float('-inf'), float('inf')
    for right in range(len(items)):
        count[items[right][1]] += 1
        if count[items[right][1]] == 1: covered += 1
        while covered == need:
            if items[right][0] - items[left][0] < best_hi - best_lo: best_lo, best_hi = items[left][0], items[right][0]
            count[items[left][1]] -= 1
            if count[items[left][1]] == 0: covered -= 1
            left += 1
    return [best_lo, best_hi]

function smallestRange(nums: number[][]): number[] {
  const items: [number, number][] = [];
  nums.forEach((list, id) => list.forEach((v) => items.push([v, id])));
  items.sort((a, b) => a[0] - b[0]);
  const need = nums.length;
  const count = new Array<number>(need).fill(0);
  let covered = 0, left = 0;
  let best = [-Infinity, Infinity];
  for (let right = 0; right < items.length; right++) {
    if (count[items[right][1]]++ === 0) covered++;
    while (covered === need) {
      if (items[right][0] - items[left][0] < best[1] - best[0]) best = [items[left][0], items[right][0]];
      if (--count[items[left][1]] === 0) covered--;
      left++;
    }
  }
  return best;
}

vector<int> smallestRange(vector<vector<int>>& nums) {
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> heap; // {value, list, index}
    long long mx = INT_MIN;
    for (int id = 0; id < (int)nums.size(); id++) {
        heap.push({nums[id][0], id, 0});
        mx = max(mx, (long long)nums[id][0]);
    }
    long long bestLo = INT_MIN, bestHi = INT_MAX;
    for (;;) {
        auto [value, id, idx] = heap.top(); heap.pop();
        if (mx - value < bestHi - bestLo) { bestLo = value; bestHi = mx; }
        if (idx + 1 == (int)nums[id].size()) break;
        int next = nums[id][idx + 1];
        heap.push({next, id, idx + 1});
        mx = max(mx, (long long)next);
    }
    return {(int)bestLo, (int)bestHi};
}

public int[] smallestRange(List<List<Integer>> nums) {
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); // {value, list, index}
    long max = Integer.MIN_VALUE;
    for (int id = 0; id < nums.size(); id++) {
        heap.add(new int[]{nums.get(id).get(0), id, 0});
        max = Math.max(max, nums.get(id).get(0));
    }
    long bestLo = Integer.MIN_VALUE, bestHi = Integer.MAX_VALUE;
    while (true) {
        int[] top = heap.poll();
        int value = top[0], id = top[1], idx = top[2];
        if (max - value < bestHi - bestLo) { bestLo = value; bestHi = max; }
        if (idx + 1 == nums.get(id).size()) break;
        int next = nums.get(id).get(idx + 1);
        heap.add(new int[]{next, id, idx + 1});
        max = Math.max(max, next);
    }
    return new int[]{(int) bestLo, (int) bestHi};
}

def smallest_range(nums):
    heap = []  # (value, list, index)
    mx = float('-inf')
    for i, lst in enumerate(nums):
        heapq.heappush(heap, (lst[0], i, 0))
        mx = max(mx, lst[0])
    best_lo, best_hi = float('-inf'), float('inf')
    while True:
        value, i, idx = heapq.heappop(heap)
        if mx - value < best_hi - best_lo: best_lo, best_hi = value, mx
        if idx + 1 == len(nums[i]): break
        nxt = nums[i][idx + 1]
        heapq.heappush(heap, (nxt, i, idx + 1))
        mx = max(mx, nxt)
    return [best_lo, best_hi]

function smallestRange(nums: number[][]): number[] {
  const heap = new Heap<number[]>((a, b) => a[0] < b[0]);
  let max = -Infinity;
  nums.forEach((list, id) => {
    heap.push([list[0], id, 0]);
    max = Math.max(max, list[0]);
  });
  let best = [-Infinity, Infinity];
  for (;;) {
    const [value, id, idx] = heap.pop();
    if (max - value < best[1] - best[0]) best = [value, max];
    if (idx + 1 === nums[id].length) break;
    const next = nums[id][idx + 1];
    heap.push([next, id, idx + 1]);
    max = Math.max(max, next);
  }
  return best;
}

class Heap<T> {
  private a: T[] = [];
  constructor(private before: (x: T, y: T) => boolean) {}
  get size() { return this.a.length; }
  peek(): T { return this.a[0]; }
  push(v: T) {
    const a = this.a;
    a.push(v);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.before(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop(): T {
    const a = this.a;
    const top = a[0];
    const last = a.pop()!;
    if (a.length) {
      a[0] = last;
      let i = 0;
      for (;;) {
        let m = i;
        const l = 2 * i + 1, r = l + 1;
        if (l < a.length && this.before(a[l], a[m])) m = l;
        if (r < a.length && this.before(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

vector<int> smallestRange(vector<vector<int>>& nums) {
    int k = nums.size();
    if (k == 0) return {};
    for (auto& list : nums) if (list.empty()) return {};
    vector<int> pos(k, 0);
    auto later = [&](int a, int b) {
        int va = nums[a][pos[a]], vb = nums[b][pos[b]];
        return va != vb ? va > vb : a > b;
    };
    priority_queue<int, vector<int>, decltype(later)> heap(later);
    long long mx = INT_MIN;
    for (int id = 0; id < k; id++) {
        heap.push(id);
        mx = max(mx, (long long)nums[id][0]);
    }
    long long bestLo = nums[heap.top()][0], bestHi = mx;
    for (;;) {
        int id = heap.top(); heap.pop();
        long long value = nums[id][pos[id]];
        if (mx - value < bestHi - bestLo) { bestLo = value; bestHi = mx; }
        if (++pos[id] == (int)nums[id].size()) break;
        heap.push(id);
        mx = max(mx, (long long)nums[id][pos[id]]);
    }
    return {(int)bestLo, (int)bestHi};
}

public int[] smallestRange(List<List<Integer>> nums) {
    int k = nums.size();
    if (k == 0) return new int[0];
    for (List<Integer> list : nums) if (list.isEmpty()) return new int[0];
    int[] pos = new int[k];
    PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> {
        int va = nums.get(a).get(pos[a]), vb = nums.get(b).get(pos[b]);
        return va != vb ? Integer.compare(va, vb) : Integer.compare(a, b);
    });
    long max = Integer.MIN_VALUE;
    for (int id = 0; id < k; id++) {
        heap.add(id);
        max = Math.max(max, nums.get(id).get(0));
    }
    long bestLo = nums.get(heap.peek()).get(0), bestHi = max;
    while (true) {
        int id = heap.poll();
        long value = nums.get(id).get(pos[id]);
        if (max - value < bestHi - bestLo) { bestLo = value; bestHi = max; }
        if (++pos[id] == nums.get(id).size()) break;
        heap.add(id);
        max = Math.max(max, nums.get(id).get(pos[id]));
    }
    return new int[]{(int) bestLo, (int) bestHi};
}

def smallest_range(nums):
    k = len(nums)
    if k == 0 or any(len(lst) == 0 for lst in nums): return []
    pos = [0] * k
    heap = []  # (current value, list id)
    mx = float('-inf')
    for i in range(k):
        heapq.heappush(heap, (nums[i][0], i))
        mx = max(mx, nums[i][0])
    best_lo, best_hi = heap[0][0], mx
    while True:
        _, i = heapq.heappop(heap)
        value = nums[i][pos[i]]
        if mx - value < best_hi - best_lo: best_lo, best_hi = value, mx
        pos[i] += 1
        if pos[i] == len(nums[i]): break
        heapq.heappush(heap, (nums[i][pos[i]], i))
        mx = max(mx, nums[i][pos[i]])
    return [best_lo, best_hi]

function smallestRange(nums: number[][]): number[] {
  const k = nums.length;
  if (k === 0 || nums.some((list) => list.length === 0)) return [];
  const pos = new Array<number>(k).fill(0);
  const heap = new Heap<number>((a, b) => nums[a][pos[a]] < nums[b][pos[b]] || (nums[a][pos[a]] === nums[b][pos[b]] && a < b));
  let max = -Infinity;
  for (let id = 0; id < k; id++) {
    heap.push(id);
    max = Math.max(max, nums[id][0]);
  }
  let bestLo = nums[heap.peek()][0], bestHi = max;
  for (;;) {
    const id = heap.pop();
    const value = nums[id][pos[id]];
    if (max - value < bestHi - bestLo) { bestLo = value; bestHi = max; }
    if (++pos[id] === nums[id].length) break;
    heap.push(id);
    max = Math.max(max, nums[id][pos[id]]);
  }
  return [bestLo, bestHi];
}

class Heap<T> {
  private a: T[] = [];
  constructor(private before: (x: T, y: T) => boolean) {}
  get size() { return this.a.length; }
  peek(): T { return this.a[0]; }
  push(v: T) {
    const a = this.a;
    a.push(v);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.before(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop(): T {
    const a = this.a;
    const top = a[0];
    const last = a.pop()!;
    if (a.length) {
      a[0] = last;
      let i = 0;
      for (;;) {
        let m = i;
        const l = 2 * i + 1, r = l + 1;
        if (l < a.length && this.before(a[l], a[m])) m = l;
        if (r < a.length && this.before(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}