Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/632.html
632. Smallest Range Covering Elements from K Lists (Hard)
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 == k1 <= k <= 35001 <= nums[i].length <= 50-105 <= nums[i][j] <= 105nums[i]is sorted in non-decreasing order.
Related Topics:
Hash Table, Two Pointers, String
Similar Questions:
Solution 1. Two Pointers
The range can be initialized as { min(min(A)), max(max(A)) }.
For input [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]], the ans is initialized as {0, 30}.
We can gradually shrink the max value from max(max(A)) to max(min(A)), 30, 26, 24, 20, 18, 15, 12 10, 9, 5.
During this process, each max value has a corresponding greatest min value
max min
30 -> 30, 26, 24, (20)
26 -> (20)
24 -> (20)
20 -> 20, 18, (15)
...
We can use two pointers. One pointer scans the max value, and the other pointer looks for the corresponding greatest min value.
Time complexity
In the worst case, the pointers needs to scan through all the elements. Assume the maximum length of A[i] is N, then there are O(NK) elements.
For each pair of { min, max } pointed by the two pointers, we need to run the valid function to check if this range is valid, which takes O(KlogN) time.
So overall the time complexity is O(K^2 * NlogN).
// OJ: https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/
// Time: O(K^2 * NlogN)
// Space: O(NK)
class Solution {
bool valid(vector<vector<int>> &A, int mn, int mx) {
for (auto &v : A) {
if (lower_bound(begin(v), end(v), mn) == upper_bound(begin(v), end(v), mx)) return false;
}
return true;
}
public:
vector<int> smallestRange(vector<vector<int>>& A) {
set<int> s;
for (auto &v : A) {
for (int n : v) s.insert(n);
}
auto i = s.rbegin(), j = s.rbegin();
vector<int> ans = { *s.begin(), *s.rbegin() };
while (j != s.rend()) {
int mx = *i;
while (j != s.rend() && !valid(A, *j, mx)) ++j;
if (j != s.rend() && (mx - *j < ans[1] - ans[0] || (mx - *j == ans[1] - ans[0] && *j < ans[0]))) ans = { *j, mx };
if (j == i) ++j;
++i;
}
return ans;
}
};
Solution 2. Next Pointer Array + Min Heap
From each A[i] we select a single element, with which we can form a group of k numbers. The difference between the max and min values is the smallest range covering these k numbers, which in turn covers the k arrays in A.
So our goal is to find a group of numbers that can minimize the difference of its max and min values.
Let’s start this group of numbers using all the min values in each A[i]. Getting its max and min value can give us a range covering it. Then what do we do next?
Since they are all min values, we can only increase one of them. Which one should we increase so that we can possibly shrink the range? That’s the min values among those numbers.
We can use a vector<int> next(A.size()) to keep track of the next element we are going to visit. Each round we increment the next[i] whose corresponding A[i][next[i]] is the minimum in the group.
After this operation, the new maximum must be either the old max value or this new A[i][next[i]], so using a single variable can keep track of the max value of the range. For the min value, we can use a min heap to keep track of it.
Time complexity
In the worst case, we need to visit all the elements. Assume the maximum length of A[i] is N, then there are O(NK) elements.
There are K elements in the min heap. During initialization, pushing K elements into the min heap takes O(KlogK) time. Each push/pop takes O(logK) time.
So overall the time complexity is O(NKlogK).
// OJ: https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/
// Time: O(NKlogK)
// Space: O(K)
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& A) {
int N = A.size(), mx = INT_MIN;
vector<int> ans = { 0, 200001 }, next(N);
auto cmp = [&](int a, int b) { return A[a][next[a]] > A[b][next[b]]; };
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
for (int i = 0; i < N; ++i) {
pq.push(i);
mx = max(mx, A[i][0]);
}
while (true) {
int i = pq.top(), mn = A[i][next[i]];
pq.pop();
if (ans[1] - ans[0] > mx - mn || (ans[1] - ans[0] == mx - mn && mn < ans[0])) ans = { A[i][next[i]], mx };
if (++next[i] == A[i].size()) break;
pq.push(i);
mx = max(mx, A[i][next[i]]);
}
return ans;
}
};
-
class Solution { public int[] smallestRange(List<List<Integer>> nums) { int rangeLeft = 0, rangeRight = Integer.MAX_VALUE; int minRange = rangeRight - rangeLeft; int max = Integer.MIN_VALUE; int size = nums.size(); int[] next = new int[size]; PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() { public int compare(Integer num1, Integer num2) { return nums.get(num1).get(next[num1]) - nums.get(num2).get(next[num2]); } }); for (int i = 0; i < size; i++) { priorityQueue.offer(i); max = Math.max(max, nums.get(i).get(0)); } outer: for (int i = 0; i < size; i++) { List<Integer> list = nums.get(i); int length = list.size(); for (int j = 0; j < length; j++) { int min = priorityQueue.poll(); int curRange = max - nums.get(min).get(next[min]); if (curRange < minRange) { minRange = curRange; rangeLeft = nums.get(min).get(next[min]); rangeRight = max; } next[min]++; if (next[min] == nums.get(min).size()) break outer; priorityQueue.offer(min); max = Math.max(max, nums.get(min).get(next[min])); } } return new int[]{rangeLeft, rangeRight}; } } ############ 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; } } -
// OJ: https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/ // Time: O(K^2 * NlogN) // Space: O(NK) class Solution { bool valid(vector<vector<int>> &A, int mn, int mx) { for (auto &v : A) { if (lower_bound(begin(v), end(v), mn) == upper_bound(begin(v), end(v), mx)) return false; } return true; } public: vector<int> smallestRange(vector<vector<int>>& A) { set<int> s; for (auto &v : A) { for (int n : v) s.insert(n); } auto i = s.rbegin(), j = s.rbegin(); vector<int> ans = { *s.begin(), *s.rbegin() }; while (j != s.rend()) { int mx = *i; while (j != s.rend() && !valid(A, *j, mx)) ++j; if (j != s.rend() && (mx - *j < ans[1] - ans[0] || (mx - *j == ans[1] - ans[0] && *j < ans[0]))) ans = { *j, mx }; if (j == i) ++j; ++i; } 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 ############ from collections import deque class Solution(object): def smallestRange(self, nums): """ :type nums: List[List[int]] :rtype: List[int] """ k = len(nums) d = collections.defaultdict(int) tuples = [] for i in range(len(nums)): for num in nums[i]: tuples.append((num, i)) tuples.sort() length = len(tuples) left = tuples[0][0] right = tuples[-1][0] deq = deque([]) for i in range(length): num, no = tuples[i] deq.append(tuples[i]) d[no] += 1 while len(deq) > 1 and d[deq[0][1]] > 1: _num, _no = deq.popleft() d[_no] -= 1 if d[_no] == 0: del d[_no] if len(d) == k: l, r = deq[0][0], deq[-1][0] if r - l < right - left: left = l right = r return (left, right) -
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 }