Smallest range covering elements from k lists

Array Hash Table Greedy Sliding Window Sorting Heap (Priority Queue)

70.1% acceptance

Feb 20, 2026

4384

101

Find the smallest range that includes at least one number from each of k sorted lists.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
  pub fn smallest_range(nums: Vec<Vec<i32>>) -> Vec<i32> {
    // min-heap: (value, list_idx, element_idx)
    let mut heap = BinaryHeap::new();
    let mut cur_max = i32::MIN;
    for (i, list) in nums.iter().enumerate() {
      heap.push(Reverse((list[0], i, 0)));
      cur_max = cur_max.max(list[0]);
    }
    let mut best = [i32::MIN, i32::MAX];
    let mut initialized = false;
    while heap.len() == nums.len() {
      let Reverse((val, i, j)) = heap.pop().unwrap();
      if !initialized || cur_max - val < best[1] - best[0] {
        best = [val, cur_max];
        initialized = true;
      }
      if j + 1 < nums[i].len() {
        let next = nums[i][j + 1];
        cur_max = cur_max.max(next);
        heap.push(Reverse((next, i, j + 1)));
      }
    }
    best.to_vec()
  }
}