Given an array and two integers l and r , find the kth largest element in the range [ l , r ] | Python3 implementation of the approach ; Function to calculate the prefix ; Creating one based indexing ; Initializing and creating prefix array ; Creating a prefix array for every possible value in a given range ; Function to return the kth largest element in the index range [ l , r ] ; Binary searching through the 2d array and only checking the range in which the sub array is a part ; Driver code ; Creating the prefix array for the given array ; Queries ; Perform queries
MAX = 1001 NEW_LINE prefix = [ [ 0 for i in range ( MAX ) ] for j in range ( MAX ) ] NEW_LINE ar = [ 0 for i in range ( MAX ) ] NEW_LINE def cal_prefix ( n , arr ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT ar [ i + 1 ] = arr [ i ] NEW_LINE DEDENT for i in range ( 1 , 1001 , 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT prefix [ i ] [ j ] = 0 NEW_LINE DEDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT if ar [ j ] <= i : NEW_LINE INDENT k = 1 NEW_LINE DEDENT else : NEW_LINE INDENT k = 0 NEW_LINE DEDENT prefix [ i ] [ j ] = prefix [ i ] [ j - 1 ] + k NEW_LINE DEDENT DEDENT DEDENT def ksub ( l , r , n , k ) : NEW_LINE INDENT lo = 1 NEW_LINE hi = 1000 NEW_LINE while ( lo + 1 < hi ) : NEW_LINE INDENT mid = int ( ( lo + hi ) / 2 ) NEW_LINE if ( prefix [ mid ] [ r ] - prefix [ mid ] [ l - 1 ] >= k ) : NEW_LINE INDENT hi = mid NEW_LINE DEDENT else : NEW_LINE INDENT lo = mid + 1 NEW_LINE DEDENT DEDENT if ( prefix [ lo ] [ r ] - prefix [ lo ] [ l - 1 ] >= k ) : NEW_LINE INDENT hi = lo NEW_LINE DEDENT return hi NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 4 , 2 , 3 , 5 , 7 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE k = 4 NEW_LINE cal_prefix ( n , arr ) NEW_LINE queries = [ [ 1 , n , 1 ] , [ 2 , n - 2 , 2 ] , [ 3 , n - 1 , 3 ] ] NEW_LINE q = len ( queries ) NEW_LINE for i in range ( q ) : NEW_LINE INDENT print ( ksub ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] , n , queries [ i ] [ 2 ] ) ) NEW_LINE DEDENT DEDENT