Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 13

Description

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]

Constraints:

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

Solution

class Solution {
public:
  vector<int> smallestRange(vector<vector<int>>& nums) {
    using ti = tuple<int, int, int>;
    priority_queue<ti, vector<ti>, greater<ti>> pq;
    vector<int> current{INT_MAX, INT_MIN};
    int range = -1;
    for(int i = 0; i < nums.size(); ++i) {
      current[0] = min(current[0], nums[i][0]);
      current[1] = max(current[1], nums[i][0]);
      pq.push({nums[i][0], i, 0});
    }
    range = current[1] - current[0];
    if(!range) return current;
    vector<int> answer = current;
    while(pq.size() == nums.size()) {
      auto [num, indexList, index] = pq.top();
      pq.pop();
      if(nums[indexList].size() == index + 1) break;
      int newNum = nums[indexList][index + 1];
      pq.push({newNum, indexList, index + 1});
      if(newNum > current[1]) {
        current[1] = newNum;
      }
      current[0] = max(current[0], get<0>(pq.top()));
      if(current[1] - current[0] < range) {
        answer = current;
        range = current[1] - current[0];
      }
    }
    return answer;
  }
};