RUST GYM Leetcode 632 Smallest Range Covering Elements from K Lists Rust Solution

632. Smallest Range Covering Elements from K Lists

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

Example 1:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Example 2:

Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]

Example 3:

Input: nums = [[10,10],[11,11]]
Output: [10,11]

Example 4:

Input: nums = [[10],[11]]
Output: [10,11]

Example 5:

Input: nums = [[1],[2],[3],[4],[5],[6],[7]]
Output: [1,7]

Constraints:

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

Rust Solution

struct Solution;

use std::cmp::Reverse;
use std::collections::BinaryHeap;

impl Solution {
    fn smallest_range(nums: Vec<Vec<i32>>) -> Vec<i32> {
        let n = nums.len();
        let mut queue: BinaryHeap<(Reverse<i32>, usize, usize)> = BinaryHeap::new();
        let mut left = std::i32::MAX;
        let mut right = std::i32::MIN;
        for i in 0..n {
            let x = nums[i][0];
            left = left.min(x);
            right = right.max(x);
            queue.push((Reverse(x), i, 1));
        }
        let mut min = (right - left, (left, right));
        while let Some((Reverse(_), i, j)) = queue.pop() {
            if j == nums[i].len() {
                break;
            } else {
                let x = nums[i][j];
                right = right.max(x);
                queue.push((Reverse(x), i, j + 1));
                if let Some(&(Reverse(y), _, _)) = queue.peek() {
                    left = left.max(y);
                }
                let r = (right - left, (left, right));
                if r < min {
                    min = r;
                }
            }
        }
        vec![(min.1).0, (min.1).1]
    }
}

#[test]
fn test() {
    let nums = vec_vec_i32![[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]];
    let res = vec![20, 24];
    assert_eq!(Solution::smallest_range(nums), res);
}

Having problems with this solution? Click here to submit an issue on github.