Find Smallest Range Containing Elements from K Lists in C++

Suppose we have k different lists. The elements are sorted. We have to search the smallest range that includes at least one number from each of the k different lists. Here the range [a,b] is smaller than range [c,d] when b-a < d-c or a < c if b-a == d-c.

So if the input is like [[4,10,15,25,26],[0,9,14,20],[5,18,24,30]], then the output will be [14, 18]

To solve this, we will follow these steps −

• minRange := inf, maxRange := -inf, rangeSize := inf, tempMinRange := inf, tempMaxRange := -inf

• n := size of nums

• Define an array pointers of size n

• make a priority queue pq

• for initialize i := 0, when i < n, update (increase i by 1), do −

  • insert { nums[i, 0], i } into pq

  • tempMaxRange := maximum of tempMaxRange and nums[i, 0]

• while 1 is non-zero, do −

  • Define one pair temp := top of pq

  • delete element from pq

  • tempMinRange := temp.first

  • idx := second element of temp

  • if tempMaxRange - tempMinRange < rangeSize, then −

    • rangeSize := tempMaxRange - tempMinRange

    • minRange := tempMinRange

    • maxRange := tempMaxRange

  • (increase pointers[idx] by 1)

  • if pointers[idx] is same as size of nums[idx], then −

    • Come out from the loop

  • Otherwise

    • tempMaxRange := maximum of tempMaxRange and nums[idx, pointers[idx]]

    • insert { nums[idx, pointers[idx]], idx } into pq

• Define an array ans of size 2

• ans[0] := minRange, ans[1] := maxRange

• return ans

Example 

Let us see the following implementation to get better understanding −

 Live Demo

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
struct Comparator{
   bool operator() (pair <int, int> a, pair <int, int> b){
      return !(a.first < b.first);
   }
};
class Solution {
public:
   vector<int> smallestRange(vector<vector<int>>& nums) {
      int minRange = INT_MAX;
      int maxRange = INT_MIN;
      int rangeSize = INT_MAX;
      int tempMinRange, tempMaxRange, tempRangeSize;
      tempMinRange = INT_MAX;
      tempMaxRange = INT_MIN;
      int n = nums.size();
      vector <int> pointers(n);
      priority_queue < pair <int, int>, vector < pair <int, int> >, Comparator > pq;
      for(int i = 0; i < n; i++){
         pq.push({nums[i][0], i});
         tempMaxRange = max(tempMaxRange, nums[i][0]);
      }
      while(1){
         pair <int, int> temp = pq.top();
         pq.pop();
         tempMinRange = temp.first;
         int idx = temp.second;
         if(tempMaxRange - tempMinRange < rangeSize){
            rangeSize = tempMaxRange - tempMinRange;
            minRange = tempMinRange;
            maxRange = tempMaxRange;
         }
         pointers[idx]++;
         if(pointers[idx] == nums[idx].size())break;
         else{
            tempMaxRange = max(tempMaxRange,
            nums[idx][pointers[idx]]);
            pq.push({nums[idx][pointers[idx]], idx});
         }
      }
      vector <int> ans(2);
      ans[0] = minRange;
      ans[1] = maxRange;
      return ans;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v =
   {{4,10,15,25,26},{0,9,14,20},{5,18,24,30}};
   print_vector(ob.smallestRange(v));
}

Input

{{4,10,15,25,26},{0,9,14,20},{5,18,24,30}};

Output

[14, 18, ]