Given an array and two integers l and r , find the kth largest element in the range [ l , r ] | Javascript 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
let MAX = 101 ; let prefix = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) { prefix [ i ] = new Array ( MAX ) . fill ( 0 ) } let ar = new Array ( MAX ) . fill ( 0 ) ; function cal_prefix ( n , arr ) { for ( let i = 0 ; i < n ; i ++ ) ar [ i + 1 ] = arr [ i ] ; for ( let i = 1 ; i < MAX ; i ++ ) { for ( let j = 0 ; j <= n ; j ++ ) prefix [ i ] [ j ] = 0 ; for ( let j = 1 ; j <= n ; j ++ ) { prefix [ i ] [ j ] = prefix [ i ] [ j - 1 ] + ( ar [ j ] <= i ? 1 : 0 ) ; } } } function ksub ( l , r , n , k ) { let lo = 1 ; let hi = MAX - 1 ; while ( lo + 1 < hi ) { let mid = Math . floor ( ( lo + hi ) / 2 ) ; if ( prefix [ mid ] [ r ] - prefix [ mid ] [ l - 1 ] >= k ) hi = mid ; else lo = mid + 1 ; } if ( prefix [ lo ] [ r ] - prefix [ lo ] [ l - 1 ] >= k ) hi = lo ; return hi ; } let arr = new Array ( 1 , 4 , 2 , 3 , 5 , 7 , 6 ) ; let n = arr . length ; let k = 4 ; cal_prefix ( n , arr ) ; let queries = new Array ( new Array ( 1 , n , 1 ) , new Array ( 2 , n - 2 , 2 ) , new Array ( 3 , n - 1 , 3 ) ) ; let q = queries . length ; for ( let i = 0 ; i < q ; i ++ ) document . write ( ksub ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] , n , queries [ i ] [ 2 ] ) + " " ) ;