Solution

Approach #1 Brute Force [Time Limit Exceeded]

The naive approach is to consider every pair of elements, $$nums[i][j]$$ and $$nums[k][l]$$ from amongst the given \nlists and consider the range formed by these elements. For every range currently considered, we can traverse over all the \nlists to find if atleast one element from these lists can be included in the current range. If so, we store the end-points of the current range \nand compare it with the previous minimum range found, if any, satisfying the required criteria, to find the smaller range from among them.

Once all the element pairs have been considered as the ranges, we can obtain the required minimum range.

Complexity Analysis

\n
• \n

  Time complexity : $$O(n^3)$$ . Considering every possible range(element pair) requires $$O(n^2)$$ time. For each range considered, \nwe need to traverse over all the elements of the given lists in the worst case requiring another $$O(n)$$ time. Here, $$n$$ refers to the \ntotal number of elements in the given lists.

  \n
\n
• \n

  Space complexity : $$O(1)$$ . Constant extra space is used.

  \n
\n

Approach #2 Better Brute Force [Time Limit Exceeded]

Algorithm

In the last approach, we consider every possible range and then traverse over every list to check if atleast one of the \nelements from these lists lies in the required range. Instead of doing this traversal for every range, we can make use \nof Binary Search to find the index of the element just larger than(or equal to) the lower limit of the range currently \nconsidered.

If all the elements in the current list are lesser than this lower limit, we\'ll get the index as $$nums[k].length$$ \n for the $$k^{th}$$ list being currently checked. In this case, none of the elements of the current list lies in the\ncurrent range.

On the other hand, if all the elements in this list are larger than this lower limit, we\'ll get the index of the first element(minimum) in the current list. If this element happens to be larger than the upper limit of the range currently considered, then also, none of the elements of the current list lies within the current range.

Whenever a range is found which satisfies the required criteria, we can compare it with the minimum range found so far \n to determine the required minimum range.

Complexity Analysis

\n
• \n

  Time complexity : $$O\\big(n^2log(k)\\big)$$ . The time required to consider every possible range is $$O(n^2)$$ . For every range currently considered, \na Binary Search requiring $$O\\big(log(k)\\big)$$ time is required. Here, $$n$$ refers to the total number of elements in the given \nlists and $$k$$ refers to the average length of each list.

  \n
\n
• \n

  Space complexity : $$O(1)$$ . Constant extra space is used.

  \n
\n

Approach #3 Using Pointers [Time Limit Exceeded]

Algorithm

We\'ll discuss about the implementation used in the current approach along with the idea behind it.

This approach makes use of an array of pointers, $$next$$ , whose length is equal to the number of given lists. In this \narray, $$next[i]$$ refers to the element which needs to be considered next in the $$(i-1)^{th}$$ list. The meaning of this will become \nmore clearer when we look at the process.

We start by initializing all the elements of $$next$$ to 0. Thus, currently, we are considering the first(minimum) element \namong all the lists. Now, we find out the index of the list containing the maximum( $$max_i$$ ) and minimum( $$min_i$$ ) \nelements from amongst the elements currently pointed by $$next$$ . The range formed by these maximum and minimum elements surely
\ncontains atleast one element from each list.

But, now our objective is to minimize this range. To do so, there are two options: Either decrease the maximum value or increase the \nminimum value.

Now, the maximum value can\'t be reduced any further, since it already corresponds to the minimum value in one of the lists. \nReducing it any further will lead to the exclusion of all the elements of this list(containing the last maximum value) \nfrom the new range.

Thus, the only option left in our hand is to try to increase the minimum value. To do so, we now need to consider the\n next element in the list containing the last minimum value. Thus, we increment the entry at the corresponding index\n in $$next$$ , to indicate that the next element in this list now needs to be considered.

Thus, at every step, we find the maximum and minimum values being pointed currently, update the $$next$$ values \n appropriately, and also find out the range formed by these maximum and minimum values to find out the smallest range \n satisfying the given criteria.

While doing this process, if any of the lists gets completely exhausted, it means that the minimum value being increased for \n minimizing the range being considered can\'t be increased any further, without causing the exclusion of all the elements in atleast \n one of the lists. Thus, we can stop the search process whenever any list gets completely exhausted.

We can also stop the process, when all the elements of the given lists have been exhausted.

Summarizing the statements above, the process becomes:

\n
1. \n

   Initialize $$next$$ array(pointers) with all 0\'s.

   \n
\n
2. \n

   Find the indices of the lists containing the minimum( $$min_i$$ ) and the maximum( $$max_i$$ ) elements amongst the elements pointed by the $$next$$ array.

   \n
\n
3. \n

   If the range formed by the maximum and minimum elements found above is larger than the previous maximum range, update the boundary values used for the maximum range.

   \n
\n
4. \n

   Increment the pointer $$nums[min_i]$$ .

   \n
\n
5. \n

   Repeat steps 2 to 4 till any of the lists gets exhausted.

   \n
\n

The animation below illustrates the process for a visual understanding of the process.

!?!../Documents/632_Smallest_Range.json:1000,563!?!

Complexity Analysis

\n
• \n

  Time complexity : $$O(n*m)$$ . In the worst case, we need to traverse over $$next$$ array(of length $$m$$ ) for all the elements of the given lists.\nHere, $$n$$ refers to the total number of elements in all the lists. $$m$$ refers to the total number of lists.

  \n
\n
• \n

  Space complexity : $$O(m)$$ . $$next$$ array of size $$m$$ is used.

  \n
\n

Approach #4 Using Priority Queue [Accepted]:

Algorithm

In the last approach, at each step, we update the pointer corresponding to the current minimum element and traverse over the whole\n $$next$$ array to determine the new maximum and minimum values. We can do some optimization here, by making use of a simple observation.

Whenever we update a single entry of $$next$$ to consider the new maximum and minimum values(if we already know the last maximum \nand minimum values), all the elements to be considered for finding the maximum and minimum values remain the same except the new element \nbeing pointed by a single updated entry in $$next$$ . This new entry is certainly larger than the last minimum value(since that was the \nreasoning behind the updation).

Thus, we can\'t be sure whether this is the new minimum element or not. But, since it is larger than the last \nvalue being considered, it could be a potential competitor for the new maximum value. Thus, we can directly compare it with the last \nmaximum value to determine the current maximum value.

Now, we\'re left with finding the minimum value iteratively at every step. To avoid this iterative process, a better idea \nis to make use of a Min-Heap, which stores the values being pointed currently by the $$next$$ array. Thus, the minimum value always \nlies at the top of this heap, and we need not do the iterative search process.

At every step, we remove the minimum element from this heap and find out the range formed by the current maximum and minimum values, and \ncompare it with the minimum range found so far to determine the required minimum range. We also update the increment the index in $$next$$ \ncorresponding to the list containing this minimum entry and add this element to the heap as well.

The rest of the process remains the same as the last approach.

Complexity Analysis

\n
• \n

  Time complexity : $$O\\big(n*log(m)\\big)$$ . Heapification of $$m$$ elements requires $$O\\big(log(m)\\big)$$ time. This step could be done \nfor all the elements of the given lists in the worst case. Here, $$n$$ refers to the total number of elements in \nall the lists. $$m$$ refers to the total number of lists.

  \n
\n
• \n

  Space complexity : $$O(m)$$ . $$next$$ array of size $$m$$ is used. A Min-Heap with $$m$$ elements is also used.

  \n
\n

Analysis written by: @vinod23