Find smallest range containing elements from k lists | Python3 program to finds out smallest range that includes elements from each of the given sorted lists . ; array for storing the current index of list i ; This function takes an k sorted lists in the form of 2D array as an argument . It finds out smallest range that includes elements from each of the k lists . ; initializing to 0 index ; for maintaining the index of list containing the minimum element ; iterating over all the list ; if every element of list [ i ] is traversed then break the loop ; find minimum value among all the list elements pointing by the ptr [ ] array ; update the index of the list ; find maximum value among all the list elements pointing by the ptr [ ] array ; if any list exhaust we will not get any better answer , so break the while loop ; updating the minrange ; Driver code
N = 5 NEW_LINE ptr = [ 0 for i in range ( 501 ) ] NEW_LINE def findSmallestRange ( arr , n , k ) : NEW_LINE INDENT i , minval , maxval , minrange , minel , maxel , flag , minind = 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 NEW_LINE for i in range ( k + 1 ) : NEW_LINE INDENT ptr [ i ] = 0 NEW_LINE DEDENT minrange = 10 ** 9 NEW_LINE while ( 1 ) : NEW_LINE INDENT minind = - 1 NEW_LINE minval = 10 ** 9 NEW_LINE maxval = - 10 ** 9 NEW_LINE flag = 0 NEW_LINE for i in range ( k ) : NEW_LINE INDENT if ( ptr [ i ] == n ) : NEW_LINE INDENT flag = 1 NEW_LINE break NEW_LINE DEDENT if ( ptr [ i ] < n and arr [ i ] [ ptr [ i ] ] < minval ) : NEW_LINE INDENT minind = i NEW_LINE minval = arr [ i ] [ ptr [ i ] ] NEW_LINE DEDENT if ( ptr [ i ] < n and arr [ i ] [ ptr [ i ] ] > maxval ) : NEW_LINE INDENT maxval = arr [ i ] [ ptr [ i ] ] NEW_LINE DEDENT DEDENT if ( flag ) : NEW_LINE INDENT break NEW_LINE DEDENT ptr [ minind ] += 1 NEW_LINE if ( ( maxval - minval ) < minrange ) : NEW_LINE INDENT minel = minval NEW_LINE maxel = maxval NEW_LINE minrange = maxel - minel NEW_LINE DEDENT DEDENT print ( " The ▁ smallest ▁ range ▁ is ▁ [ " , minel , maxel , " ] " ) NEW_LINE DEDENT arr = [ [ 4 , 7 , 9 , 12 , 15 ] , [ 0 , 8 , 10 , 14 , 20 ] , [ 6 , 12 , 16 , 30 , 50 ] ] NEW_LINE k = len ( arr ) NEW_LINE findSmallestRange ( arr , N , k ) NEW_LINE