human
Give me a code to maximize median of a KxK sub and the other steps required given the following:
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"
Solution in Python:
assistant
#Here is code to maximize median of a KxK sub and the other steps required.
 def isMaximumMedian ( arr , N , K , mid ) :
	Pre = [ [ 0 for x in range ( N + 5 ) ] for y in range ( N + 5 ) ]
	for i in range ( N ) :
		for j in range ( N ) :
			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 ] += 1
	required = ( K * K + 1 ) // 2
	flag = 0
	for i in range ( K , N + 1 ) :
		for j in range ( K , N + 1 ) :
			X = ( Pre [ i ] [ j ] - Pre [ i - K ] [ j ] - Pre [ i ] [ j - K ] + Pre [ i - K ] [ j - K ] )
			if ( X < required ) :
				flag = 1
	return flag
def maximumMedian ( arr , N , K ) :
	low = 0
	high = 1000000009
	while ( low < high ) :
		mid = low + ( high - low ) // 2
		if ( isMaximumMedian ( arr , N , K , mid ) ) :
			low = mid + 1
		else :
			high = mid
	return low
if __name__ == " _ _ main _ _ " :
	arr = [ [ 1 , 5 , 12 ] , [ 6 , 7 , 11 ] , [ 8 , 9 , 10 ] ]
	N = len ( arr )
	K = 2
	print ( maximumMedian ( arr , N , K ) )