Given an array and two integers l and r , find the kth largest element in the range [ l , r ] | PHP 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
< ? php $ MAX = 101 ; $ prefix = array_fill ( 0 , $ MAX , array_fill ( 0 , $ MAX , 0 ) ) ; $ ar = array_fill ( 0 , $ MAX , 0 ) ; function cal_prefix ( $ n , $ arr ) { global $ prefix , $ ar , $ MAX ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ ar [ $ i + 1 ] = $ arr [ $ i ] ; for ( $ i = 1 ; $ i < $ MAX ; $ i ++ ) { for ( $ j = 0 ; $ j <= $ n ; $ j ++ ) $ prefix [ $ i ] [ $ j ] = 0 ; for ( $ j = 1 ; $ j <= $ n ; $ j ++ ) { $ prefix [ $ i ] [ $ j ] = $ prefix [ $ i ] [ $ j - 1 ] + ( int ) ( $ ar [ $ j ] <= $ i ? 1 : 0 ) ; } } } function ksub ( $ l , $ r , $ n , $ k ) { global $ prefix , $ ar , $ MAX ; $ lo = 1 ; $ hi = $ MAX - 1 ; while ( $ lo + 1 < $ hi ) { $ mid = ( int ) ( ( $ 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 ; } $ arr = array ( 1 , 4 , 2 , 3 , 5 , 7 , 6 ) ; $ n = count ( $ arr ) ; $ k = 4 ; cal_prefix ( $ n , $ arr ) ; $ queries = array ( array ( 1 , $ n , 1 ) , array ( 2 , $ n - 2 , 2 ) , array ( 3 , $ n - 1 , 3 ) ) ; $ q = count ( $ queries ) ; for ( $ i = 0 ; $ i < $ q ; $ i ++ ) echo ksub ( $ queries [ $ i ] [ 0 ] , $ queries [ $ i ] [ 1 ] , $ n , $ queries [ $ i ] [ 2 ] ) . " STRNEWLINE " ; ? >