Smallest submatrix with Kth maximum XOR | Java Program for above approach ; 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
import java . util . * ; import java . lang . * ; class GFG { static void smallestPosition ( int m [ ] [ ] , int k ) { int n = m . length ; int mm = m [ 0 ] . length ; int [ ] [ ] xor = new int [ n ] [ mm ] ; PriorityQueue < Integer > minHeap = new PriorityQueue < > ( ) ; Map < Integer , int [ ] > map = new HashMap < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < mm ; j ++ ) { int a = i - 1 >= 0 ? xor [ i - 1 ] [ j ] : 0 ; int b = j - 1 >= 0 ? xor [ i ] [ j - 1 ] : 0 ; int c = ( i - 1 >= 0 && j - 1 >= 0 ) ? xor [ i - 1 ] [ j - 1 ] : 0 ; xor [ i ] [ j ] = m [ i ] [ j ] ^ a ^ b ^ c ; minHeap . add ( xor [ i ] [ j ] ) ; if ( minHeap . size ( ) > k ) { minHeap . poll ( ) ; } if ( ! map . containsKey ( xor [ i ] [ j ] ) ) map . put ( xor [ i ] [ j ] , new int [ ] { i , j } ) ; } } int kth_max_e = minHeap . poll ( ) ; System . out . println ( ( map . get ( kth_max_e ) [ 0 ] + 1 ) + " ▁ " + ( map . get ( kth_max_e ) [ 1 ] + 1 ) ) ; } public static void main ( String [ ] args ) { int m [ ] [ ] = { { 1 , 2 , 3 } , { 2 , 2 , 1 } , { 2 , 4 , 2 } } ; int k = 1 ; smallestPosition ( m , k ) ; } }