Welcome to Subscribe On Youtube
632. Smallest Range Covering Elements from K Lists
Description
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]
Constraints:
nums.length == k1 <= k <= 35001 <= nums[i].length <= 50-105 <= nums[i][j] <= 105nums[i]is sorted in non-decreasing order.
Solutions
Solution 1: Sorting + Sliding Window
We construct a data item $(x, i)$ for each number $x$ and its group $i$, and store these items in a new array $t$. Then, we sort $t$ by the value of the numbers (similar to merging multiple sorted arrays into a new sorted array).
Next, we traverse each data item in $t$, focusing on the group to which each number belongs. We use a hash table to record the groups of numbers within the sliding window. If the number of groups is $k$, it means the current window meets the problem’s requirements. At this point, we calculate the start and end positions of the window and update the answer.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the total number of numbers in all arrays.
Solution 2: Priority Queue (Heap)
This implementation uses breadth-first search, followed by heap, followed by sliding window. It traverses the relevant values and updates its state as each value is processed. The auxiliary container determines which pending state is processed next. After all required states have been considered, the maintained result is returned.
-
class Solution { public int[] smallestRange(List<List<Integer>> nums) { int n = 0; for (var v : nums) { n += v.size(); } int[][] t = new int[n][2]; int k = nums.size(); for (int i = 0, j = 0; i < k; ++i) { for (int x : nums.get(i)) { t[j++] = new int[] {x, i}; } } Arrays.sort(t, (a, b) -> a[0] - b[0]); int j = 0; Map<Integer, Integer> cnt = new HashMap<>(); int[] ans = new int[] {-1000000, 1000000}; for (int[] e : t) { int b = e[0]; int v = e[1]; cnt.put(v, cnt.getOrDefault(v, 0) + 1); while (cnt.size() == k) { int a = t[j][0]; int w = t[j][1]; int x = b - a - (ans[1] - ans[0]); if (x < 0 || (x == 0 && a < ans[0])) { ans[0] = a; ans[1] = b; } cnt.put(w, cnt.get(w) - 1); if (cnt.get(w) == 0) { cnt.remove(w); } ++j; } } return ans; } } -
class Solution { public: vector<int> smallestRange(vector<vector<int>>& nums) { int n = 0; for (auto& v : nums) n += v.size(); vector<pair<int, int>> t(n); int k = nums.size(); for (int i = 0, j = 0; i < k; ++i) { for (int v : nums[i]) { t[j++] = {v, i}; } } sort(t.begin(), t.end()); int j = 0; unordered_map<int, int> cnt; vector<int> ans = {-1000000, 1000000}; for (int i = 0; i < n; ++i) { int b = t[i].first; int v = t[i].second; ++cnt[v]; while (cnt.size() == k) { int a = t[j].first; int w = t[j].second; int x = b - a - (ans[1] - ans[0]); if (x < 0 || (x == 0 && a < ans[0])) { ans[0] = a; ans[1] = b; } if (--cnt[w] == 0) { cnt.erase(w); } ++j; } } return ans; } }; -
class Solution: def smallestRange(self, nums: List[List[int]]) -> List[int]: t = [(x, i) for i, v in enumerate(nums) for x in v] t.sort() cnt = Counter() ans = [-inf, inf] j = 0 for b, v in t: cnt[v] += 1 while len(cnt) == len(nums): a = t[j][0] x = b - a - (ans[1] - ans[0]) if x < 0 or (x == 0 and a < ans[0]): ans = [a, b] w = t[j][1] cnt[w] -= 1 if cnt[w] == 0: cnt.pop(w) j += 1 return ans -
func smallestRange(nums [][]int) []int { t := [][]int{} for i, x := range nums { for _, v := range x { t = append(t, []int{v, i}) } } sort.Slice(t, func(i, j int) bool { return t[i][0] < t[j][0] }) ans := []int{-1000000, 1000000} j := 0 cnt := map[int]int{} for _, x := range t { b, v := x[0], x[1] cnt[v]++ for len(cnt) == len(nums) { a, w := t[j][0], t[j][1] x := b - a - (ans[1] - ans[0]) if x < 0 || (x == 0 && a < ans[0]) { ans[0], ans[1] = a, b } cnt[w]-- if cnt[w] == 0 { delete(cnt, w) } j++ } } return ans } -
impl Solution { pub fn smallest_range(nums: Vec<Vec<i32>>) -> Vec<i32> { let mut t = vec![]; for (i, x) in nums.iter().enumerate() { for &v in x { t.push((v, i)); } } t.sort_unstable(); let (mut ans, n) = (vec![-1000000, 1000000], nums.len()); let mut j = 0; let mut cnt = std::collections::HashMap::new(); for (b, v) in t.iter() { let (b, v) = (*b, *v); if let Some(x) = cnt.get_mut(&v) { *x += 1; } else { cnt.insert(v, 1); } while cnt.len() == n { let (a, w) = t[j]; let x = b - a - (ans[1] - ans[0]); if x < 0 || (x == 0 && a < ans[0]) { ans = vec![a, b]; } if let Some(x) = cnt.get_mut(&w) { *x -= 1; } if cnt[&w] == 0 { cnt.remove(&w); } j += 1; } } ans } } -
const smallestRange = (nums: number[][]): number[] => { const pq = new PriorityQueue<number[]>((a, b) => a[0] - b[0]); const n = nums.length; let [l, r, max] = [0, Number.POSITIVE_INFINITY, Number.NEGATIVE_INFINITY]; for (let j = 0; j < n; j++) { const x = nums[j][0]; pq.enqueue([x, j, 0]); max = Math.max(max, x); } while (pq.size() === n) { const [min, j, i] = pq.dequeue(); if (max - min < r - l) { [l, r] = [min, max]; } const iNext = i + 1; if (iNext < nums[j].length) { const next = nums[j][iNext]; pq.enqueue([next, j, iNext]); max = Math.max(max, next); } } return [l, r]; }; -
const smallestRange = nums => { const pq = new PriorityQueue((a, b) => a[0] - b[0]); const n = nums.length; let [l, r, max] = [0, Number.POSITIVE_INFINITY, Number.NEGATIVE_INFINITY]; for (let j = 0; j < n; j++) { const x = nums[j][0]; pq.enqueue([x, j, 0]); max = Math.max(max, x); } while (pq.size() === n) { const [min, j, i] = pq.dequeue(); if (max - min < r - l) { [l, r] = [min, max]; } const iNext = i + 1; if (iNext < nums[j].length) { const next = nums[j][iNext]; pq.enqueue([next, j, iNext]); max = Math.max(max, next); } } return [l, r]; };