Maximize median of a KxK sub | Function to determine if a given value can be median ; Stores the prefix sum array ; Traverse the matrix arr [ ] [ ] ; Update Pre [ i + 1 ] [ j + 1 ] ; If arr [ i ] [ j ] is less than or equal to mid ; Stores the count of elements should be less than mid ; Stores if the median mid can be possible or not ; Iterate over the range [ K , N ] ; Iterate over the range [ K , N ] ; Stores count of elements less than or equal to the value mid in submatrix with bottom right vertices at ( i , j ) ; If X is less than or equal to required ; Return flag ; Function to find the maximum median of a subsquare of the given size ; Stores the range of the search space ; Iterate until low is less than high ; Stores the mid value of the range [ low , high ] ; If the current median can be possible ; Update the value of low ; Update the value of high ; Return value stored in low as answer ; Driver Code
function isMaximumMedian ( arr , N , K , mid ) { let Pre = Array ( N + 5 ) . fill ( ) . map ( ( ) => Array ( N + 5 ) . fill ( 0 ) ) ; for ( let i = 0 ; i < N ; ++ i ) { for ( let j = 0 ; j < N ; ++ j ) { Pre [ i + 1 ] [ j + 1 ] = Pre [ i + 1 ] [ j ] + Pre [ i ] [ j + 1 ] - Pre [ i ] [ j ] ; if ( arr [ i ] [ j ] <= mid ) Pre [ i + 1 ] [ j + 1 ] ++ ; } } let required = Math . floor ( ( K * K + 1 ) / 2 ) ; let flag = 0 ; for ( let i = K ; i <= N ; ++ i ) { for ( let j = K ; j <= N ; ++ j ) { let X = Pre [ i ] [ j ] - Pre [ i - K ] [ j ] - Pre [ i ] [ j - K ] + Pre [ i - K ] [ j - K ] ; if ( X < required ) flag = 1 ; } } return flag ; } function maximumMedian ( arr , N , K ) { let low = 0 , high = 1e9 ; while ( low < high ) { let mid = low + Math . floor ( ( high - low ) / 2 ) ; if ( isMaximumMedian ( arr , N , K , mid ) ) { low = mid + 1 ; } else { high = mid ; } } return low ; } let arr = [ [ 1 , 5 , 12 ] , [ 6 , 7 , 11 ] , [ 8 , 9 , 10 ] ] ; let N = arr . length ; let K = 2 ; document . write ( maximumMedian ( arr , N , K ) ) ;