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 × log n), and the space complexity is O(n). Here, n is the total number of numbers in all arrays.
PythonJavaC++GoRust
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 i, (b, v) in enumerate(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(code-box)
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.merge(v, 1, Integer::sum);
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;
}
if (cnt.merge(w, -1, Integer::sum) == 0) {
cnt.remove(w);
}
++j;
}
}
return ans;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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
}
}(code-box)
Solution 2: Priority Queue (Heap)
TypeScriptJavaScript
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];
};(code-box)
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];
};(code-box)
