632. 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.

C++

• 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;
      }
  };

PYTHON

• class Solution:
      def smallestRange(self, nums):
          n = sum(len(v) for v in nums)
          t = []
          k = len(nums)
          for i, v in enumerate(nums):
              for x in v:
                  t.append((x, i))
          t.sort()
          j = 0
          cnt = {}
          ans = [-1000000, 1000000]
          for i in range(n):
              b, v = t[i]
              cnt[v] = cnt.get(v, 0) + 1
              while len(cnt) == k:
                  a, w = t[j]
                  x = b - a - (ans[1] - ans[0])
                  if x < 0 or (x == 0 and a < ans[0]):
                      ans = [a, b]
                  cnt[w] -= 1
                  if cnt[w] == 0:
                      del cnt[w]
                  j += 1
          return ans

JAVA

• 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;
      }
  }