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
def isMaximumMedian ( arr , N , K , mid ) : NEW_LINE INDENT Pre = [ [ 0 for x in range ( N + 5 ) ] for y in range ( N + 5 ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( N ) : NEW_LINE INDENT Pre [ i + 1 ] [ j + 1 ] = ( Pre [ i + 1 ] [ j ] + Pre [ i ] [ j + 1 ] - Pre [ i ] [ j ] ) NEW_LINE if ( arr [ i ] [ j ] <= mid ) : NEW_LINE INDENT Pre [ i + 1 ] [ j + 1 ] += 1 NEW_LINE DEDENT DEDENT DEDENT required = ( K * K + 1 ) // 2 NEW_LINE flag = 0 NEW_LINE for i in range ( K , N + 1 ) : NEW_LINE INDENT for j in range ( K , N + 1 ) : NEW_LINE INDENT X = ( Pre [ i ] [ j ] - Pre [ i - K ] [ j ] - Pre [ i ] [ j - K ] + Pre [ i - K ] [ j - K ] ) NEW_LINE if ( X < required ) : NEW_LINE INDENT flag = 1 NEW_LINE DEDENT DEDENT DEDENT return flag NEW_LINE DEDENT def maximumMedian ( arr , N , K ) : NEW_LINE INDENT low = 0 NEW_LINE high = 1000000009 NEW_LINE while ( low < high ) : NEW_LINE INDENT mid = low + ( high - low ) // 2 NEW_LINE if ( isMaximumMedian ( arr , N , K , mid ) ) : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT high = mid NEW_LINE DEDENT DEDENT return low NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ [ 1 , 5 , 12 ] , [ 6 , 7 , 11 ] , [ 8 , 9 , 10 ] ] NEW_LINE N = len ( arr ) NEW_LINE K = 2 NEW_LINE print ( maximumMedian ( arr , N , K ) ) NEW_LINE DEDENT