Smallest Range covering elements from K Lists – LeetCode

This is the eighth and last question from the STL section of our AlgoMaster Sheet. This involves all the concepts we have covered till now. If you haven’t sequentially followed our AlgoMaster sheet, we highly recommend you check all the articles sequentially otherwise you may feel lost!! The link to the Youtube Channel is- CS FOR ALL !!

Problem Statement:

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

Intuition:

As the tag suggests, the question is a little bit different and on the tougher side than most of which we have solved till now. So we highly recommend you give it a try before moving on to the solution. Do some dirty work, actually run some test cases on paper, and then come back to the article!! Now with that being said, we move to the actual solution to the question!!!

Let us see the TestCase-1 and gather some insights into how we will solve the question- Given a vector of vector, that is, a 2D vector, we need to find the smallest range inside which covers at least one element from each vector. What we mean by this is- the range we must return should include at least one element from each vector from the set of vectors given to us. Let us take a deep dive into the question!! Also, we must keep in mind that all the vectors inside the vector of vectors are sorted within themselves!!

For TestCase -1, the set of vectors given to us are- [ [4,10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30] ]. The vectors are sorted within themselves. So we need to find the minimum and maximum values from these given vectors. The range will be equal maxTillNow – minElement. The data structure that we would be using is a Min-Heap or Priority Queue. Why you can ask right? Simple- we need to find the minimum among all the sets of numbers- that’s why we are using a Priority Queue or a Min-Heap to ease our work at each process. Otherwise, we will encounter TLE in this problem!!

However, we can’t simply use a normal Priority-Queue, we can use a pair<int, pair<int, int>> or simply a vector of Priority-Queue. The vector is of size 3 and every index will represent a unique value- Index 0: Current Element which is to be added into the queue, Index 1: Index of the current element inside the given vector, Index 2: Index of the given vector for the nums[][].

Initially, we will put all the first elements from every vector inside our Min-Heap along with the index of that element inside the vector and the index of that vector for the vector of vector!! Still, getting confused? Let me clarify a bit more- we are having a vector of vectors that is, 2D vector nums[][], for each vector we will be having an index and, every vector will have its index inside the nums[][]. Make sure you understand every term before moving forward!!

So, our approach will be like this- store all the first elements of every vector present in nums[][] at index 0, index 1 will contain their indices [which in this case is 0], and the index of every vector for the nums[][]. Next, we will take out the vector having the minimum element [remember we are using Min-Heap of vectors so they will be sorted based on the First Value of each vector]. However, to calculate Range we need both Minimum as well as Maximum values right? So instead of using another Max-Heap, we will store the Max-Till-Now in a variable known as MaxTillNow.

Now comes the main part, what will be our algorithm right? It’s pretty simple- every time we will take the smallest element out, calculate the range using the minimum and maximum values, and update our StartIndex and endIndex if the curr-Range is larger than the range we have encountered till now. And to look for the minimum range, we include the next element of that vector inside our priority queue or Min-Heap. Our loop terminates once our Priority-Queue is empty or we have reached the last of any vector and we cannot traverse anymore. This is because we have to include at least one element from each vector present in nums[][]. So once we reach the end of one vector, we have to terminate our process and break out from the While Loop.

Algorithm:-

1. Since we are required to find the smallest range then it is guaranteed that lower and higher limits of the range will be from given elements.
2. We need to ensure that at least one element from all the vectors is present in that range:
3. We will push 1st element of all vectors into the priority queue( min-Heap )
4. Every time we push an element in the queue we find the maximum value
5. The top element of the priority queue will give us the lower limit of the range and the maximum value will give us a higher range ( satisfy the condition that at least one element is present from each list)
6. Now will pop the smallest element from the queue to find the minimum range we push the next element of the list whose element is at the top (to ensure that at least one element of all lists is present in the range)
7. If any list is exhausted will break the loop and return our answer.

Code:-

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        
        // Min-Heap of vector[]
        priority_queue<vector<int> , vector<vector<int>> , greater<vector<int>>> pq ;
        
        int maxTillNow = -1 ; // MaxTillNow initally will have -1
        int range = 1000000 ; // We initally assume the range as 10^7 
        int n = nums.size() ; 
        
        for(int i = 0; i < n; i++)
        {
            int val = nums[i][0] ;
            
            // Everytime our vector will have 3 values:
            // 0th Index: Current-Value 
            // 1st Index: Index of that Element 
            // 2nd Index: Index of the vector in nums[][]

            pq.push( {val , 0 , i} ) ;
            
            maxTillNow = max(maxTillNow , val) ;
        }

        // Start Index and End Index will be initally 0
        int si = 0 ;  
        int ei = 0 ;

        while(pq.empty() == false)
        {
            
            vector<int> curr = pq.top() ; // We take our the vector with the Smallest Value
            pq.pop() ; // We pop it out from the vector

            int val = curr[0] ; // Minimum Element from the Priority Queue
            int idx = curr[1] ; // Index of that Minimum Element
            int listNum = curr[2] ; // Index of the vector of which is a part nums[][]
            int size = nums[listNum].size() ; // Store the Length of that vector in which val is present
            // We calculate Range by taking (maxTillNow - val)
            
            // If our Current-Range is smaller than the Range we have calculated till now, we update Range
            if(maxTillNow - val < range) 
            {
                range = maxTillNow - val ;
                si = val ;
                ei = maxTillNow ;
            }
            
            // We break out as soon as we reach the end of one of the given vector inside nums[][]
            if(idx == size)
                break ;
            
            // We update curr[] vector with the Next-Value from the vector list and subsequently update maxTillNow

            int nextVal = nums[listNum][idx] ;
            maxTillNow = max(maxTillNow,nextVal) ;
            
            pq.push( {nextVal , idx+1 , listNum} ) ;
        }
        
        // At the end, we return the range as {startIndex , endIndex} 
        return  {si,ei} ;
    }
};

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        
        PriorityQueue<int[]> pq = new PriorityQueue<>( (a, b) -> a[0] - b[0]);
        
        int max = -1;  // max initally will have -1
        int range = 10000000;  // We initally assume the range as 10^7 
        int n = nums.size();
        
        for(int i=0; i<n; i++)
        {
            int val = nums.get(i).get(0);

            // Everytime our array will have 3 values:
            // 0th Index: Current-Value 
            // 1st Index: Index of that Element 
            // 2nd Index: Index of the list in nums

            int[] add = {val,0,i};
            pq.add(add);
            
            max = Math.max(max,val);
        }
        // Start Index and End Index will be initally 0
        int si = 0;
        int ei = 0;
        while(!pq.isEmpty())
        {
            
            int[] curr = pq.remove();  // We take out the array with the Smallest Value
            int val = curr[0]; // Minimum Element from the Priority Queue
            int idx = curr[1]; // Index of that Minimum Element
            int listNum = curr[2];  // Index of the list which is a part of nums
            int size = nums.get(listNum).size();  // Store the Length of that list in which val is present

             // We calculate Range by taking (max - val)
             // If our Current-Range is smaller than the Range we have calculated till now, we update Range
            if(max - val < range)
            {
                range = max - val;
                si = val;
                ei = max;
            }
            
            // We break out as soon as we reach the end of one of the given list inside nums
            if(idx == size)
                break;
            
            // We update add[] array with the Next-Value from the vector list and subsequently update max

            int nextVal = nums.get(listNum).get(idx);
            max = Math.max(max,nextVal);
            int add[] = {nextVal,idx+1,listNum};
            
            pq.add(add);
        }
        // At the end, we return the range as {startIndex , endIndex} 
        int ans[] = {si,ei};
        return  ans;
    }
}

Analysis of Time & Space Complexity:-

We know that insert [push()] and delete [pop()] take O(K) time complexity. We have N vectors inside nums[][] and we assume that the Average Length of each vector is K, that is, every vector on average has K Elements. Thus if we take into account the time taken to push the elements into the Priority Queue, our Time Complexity comes out as O(N * KLogK). Similarly, at any instance, we are having K Elements in our Priority Queue thus our Space Complexity is O(K).

If you have still any more doubts, make sure to check the following video by SUNYUL HOSSEN and also follow his YouTube Channel – CS FOR ALL for such amazing content!! For any questions, regarding the post, you can post down in the comment section!!

Contributors: Arghya Chatterjee: LinkedIn, Tanmay Dutta: LinkedIn, Raj Chowdhury: LinkedIn & Arjan Hazra: LinkedIn