632. Smallest Range Covering Elements from K Lists

📋 Đề Bài

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 == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-10⁵ <= nums[i][j] <= 10⁵
nums[i] is sorted in non-decreasing order.

🧠 Thuật Toán & Kỹ Thuật

Hash Table (Bảng băm)Bit Manipulation (Thao tác bit)Matrix (Ma trận)

⏱️ Thời gian O(n²)

💾 Không gian O(n)

💻 Lời Giải

C++ 0632-smallest-range-covering-elements-from-k-lists.cpp

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        using pii = pair<int, int>;
        set<pii> s;
        const int n = nums.size();
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < (int)nums[i].size(); ++j) {
                s.insert({nums[i][j], i});
            }
        }
        
        vector<pii> flatten(s.begin(), s.end());        
        vector<int> ans;
        const int sz = flatten.size();
        unordered_map<int, int> um;
        
        for (int j = 0, i = 0; i < sz; ++i) {
            um[flatten[i].second]++;
            
            while (um.size() == n) {
                if (ans.empty() || flatten[i].first - flatten[j].first < ans[1] - ans[0]) {
                    ans = {flatten[j].first, flatten[i].first};
                }
                um[flatten[j].second]--;
                if (!um[flatten[j].second]) {
                    um.erase(flatten[j].second);
                }
                j++;
            }
        }
        
        return ans;
    }
};