13. Smallest range in K lists

Given K sorted lists of integers, KSortedArray[] of size N each. The task is to find the smallest range that includes at least one element from each of the K lists. If more than one such range's are found, return the first such range found.

Example 1:

Input:
N = 5, K = 3
KSortedArray[][] = {{1 3 5 7 9},
                    {0 2 4 6 8},
                    {2 3 5 7 11}}
Output: 1 2
Explanation: K = 3
A:[1 3 5 7 9]
B:[0 2 4 6 8]
C:[2 3 5 7 11]
Smallest range is formed by number 1
present in first list and 2 is present
in both 2nd and 3rd list.

Example 2:

Input:
N = 4, K = 3
KSortedArray[][] = {{1 2 3 4},
                    {5 6 7 8},
                    {9 10 11 12}}
Output: 4 9

Solution:

Approach Given K sorted list, find a range where there is at least one element from every list. The idea to solve the problem is very simple, keep k pointers which will constitute the elements in the range, by taking the min and max of the k elements the range can be formed. Initially, all the pointers will point to the start of all the k arrays. Store the range max to min. If the range has to be minimised then either the minimum value has to be increased or maximum value has to be decreased. The maximum value cannot be decreased as the array is sorted but the minimum value can be increased. To continue increasing the minimum value, increase the pointer of the list containing the minimum value and update the range until one of the lists exhausts. Time complexity : O(n * k2), to find the maximum and minimum in an array of length k the time required is O(k), and to traverse all the k arrays of length n (in worst case), the time complexity is O(n*k), then the total time complexity is O(n*k2).

Solution: (Heap)

The approach remains the same but the time complexity can be reduced by using min-heap or priority queue. Min heap can be used to find the maximum and minimum value in logarithmic time or log k time instead of linear time

class Solution
{
public:
    pair<int, int> findSmallestRange(int arr[][N], int n, int k)
    {
        //code here
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
        pair<int, int> res;

        int maxVal = INT_MIN;

        for (int i = 0; i < k; i++)
        {
            pq.push({arr[i][0], {i, 0}});
            maxVal = max(maxVal, arr[i][0]);
        }

        int dif = maxVal - pq.top().first;
        res = {pq.top().first, maxVal};

        while (!pq.empty())
        {
            int minVal = pq.top().first;
            int minrow = pq.top().second.first;
            int minIdx = pq.top().second.second;

            if (minIdx + 1 < n)
            {
                pq.pop();
                pq.push({arr[minrow][minIdx + 1], {minrow, minIdx + 1}});
                maxVal = max(maxVal, arr[minrow][minIdx + 1]);
            }
            else
            {
                break;
            }

            int newdif = maxVal - pq.top().first;
            if (newdif < dif)
            {
                res = {pq.top().first, maxVal};
                dif = newdif;
            }
        }

        return res;
    }
};

Time complexity : O(n * k *log k)