Smallest submatrix with Kth maximum XOR | Function to print smallest index of Kth maximum Xor value of submatrices ; Dimensions of matrix ; Stores XOR values for every index ; Min heap to find the kth maximum XOR value ; Stores indices for corresponding XOR values ; Traversing matrix to calculate XOR values ; Insert calculated value in Min Heap ; If size exceeds k ; Remove the minimum ; Store smallest index containing xor [ i , j ] ; Stores the kth maximum element ; Print the required index ; Driver code ; Function call
def smallestPosition ( m , k ) : NEW_LINE INDENT n = len ( m ) NEW_LINE mm = len ( m [ 1 ] ) NEW_LINE xor = [ [ 0 for i in range ( mm ) ] for j in range ( n ) ] NEW_LINE minHeap = [ ] NEW_LINE Map = { } NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( mm ) : NEW_LINE INDENT if i - 1 >= 0 : NEW_LINE INDENT a = xor [ i - 1 ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT a = 0 NEW_LINE DEDENT if j - 1 >= 0 : NEW_LINE INDENT b = xor [ i ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT b = 0 NEW_LINE DEDENT if i - 1 >= 0 and j - 1 >= 0 : NEW_LINE INDENT c = xor [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT c = 0 NEW_LINE DEDENT xor [ i ] [ j ] = m [ i ] [ j ] ^ a ^ b ^ c NEW_LINE minHeap . append ( xor [ i ] [ j ] ) NEW_LINE minHeap . sort ( ) NEW_LINE if ( len ( minHeap ) > k ) : NEW_LINE INDENT del minHeap [ 0 ] NEW_LINE DEDENT if xor [ i ] [ j ] not in Map : NEW_LINE INDENT Map [ xor [ i ] [ j ] ] = [ i , j ] NEW_LINE DEDENT DEDENT DEDENT minHeap . sort ( ) NEW_LINE kth_max_e = minHeap [ 0 ] NEW_LINE print ( ( Map [ kth_max_e ] [ 0 ] + 1 ) , ( Map [ kth_max_e ] [ 1 ] + 1 ) ) NEW_LINE DEDENT m = [ [ 1 , 2 , 3 ] , [ 2 , 2 , 1 ] , [ 2 , 4 , 2 ] ] NEW_LINE k = 1 NEW_LINE smallestPosition ( m , k ) NEW_LINE