Smallest submatrix with Kth maximum XOR

Given a matrix m[][] of dimensions N × M and an integer K, calculate XOR(i, j) which is equal to the Bitwise Xor of all elements of submatrix from indices (1, 1) to (i, j)), for every indices of the matrix. The task is to find the submatrix {(1, 1), …, (i, j)} having Kth maximum XOR(i, j) value. If multiple such submatrices exists, then print the smallest one.

Note: Consider the starting index of the matrix from (1, 1).

Examples:

Input: m[][] = {{1, 2}, {2, 3}}, K = 2

Output: 1 2

Explanation:

XOR(1, 1) : m[1][1] = 1

XOR(1, 2): m[1][1] xor m[1][2] = 3

XOR(2, 1): m[1][1] xor m[2][1] = 3

XOR(2, 2): m[1][1] xor m[1][2] xor m[2][1] xor m[2][2] = 2

Hence, the 2nd maximum value is 3 at position [1, 2].

Input: m[][] = {{1, 2, 3}, {2, 2, 1}, {2, 4, 2} }, k = 1

Output: 3 2

Approach: The idea is to find XOR (i, j) using Dynamic Programming.

Calculate the bitwise XOR(i, j) as xor[i][j] = xor[i-1][j] ^ xor[i][j-1] ^ xor[i-1][j-1] ^ m[i][j].

Store the XOR(i, j) values obtained for respective indices (i, j) in a Map.

Find the Kth maximum of all XOR(i, j) values using a Min-heap of size K .

Find the smallest index (i, j) for which XOR(i, j) is equal to the Kth maximum obtained in th above step using the Map.

Below is the implementation of the above approach:

// Java Program for above approach 

import java.util.*; 

import java.lang.*; 

  

class GFG { 

  

    // Function to print smallest index of 

    // Kth maximum Xor value of submatrices 

    static void smallestPosition(int m[][], int k) 

    { 

  

        // Dimensions of matrix 

        int n = m.length; 

        int mm = m[0].length; 

  

        // Stores XOR values for every index 

        int[][] xor = new int[n][mm]; 

  

        // Min heap to find the 

        // kth maximum XOR value 

        PriorityQueue<Integer> minHeap 

            = new PriorityQueue<>(); 

  

        // Stores indices for 

        // corresponding XOR vlaues 

        Map<Integer, int[]> map 

            = new HashMap<>(); 

  

        // Traversing matrix to 

        // calculate XOR values 

        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; 

  

                // Insert calculated value 

                // in Min Heap 

                minHeap.add(xor[i][j]); 

  

                // If size exceeds k 

                if (minHeap.size() > k) { 

  

                    // Remove the minimum 

                    minHeap.poll(); 

                } 

  

                // Store smallest index 

                // containing xor[i][j] 

                if (!map.containsKey(xor[i][j])) 

                    map.put(xor[i][j], 

                            new int[] { i, j }); 

            } 

        } 

  

        // Stores the kth maximum element 

        int kth_max_e = minHeap.poll(); 

  

        // Print the required index 

        System.out.println( 

            (map.get(kth_max_e)[0] + 1) 

            + " " + (map.get(kth_max_e)[1] + 1)); 

    } 

    // Driver Code 

    public static void main(String[] args) 

    { 

  

        int m[][] = { { 1, 2, 3 }, 

                      { 2, 2, 1 }, 

                      { 2, 4, 2 } }; 

        int k = 1; 

  

        // Function call 

        smallestPosition(m, k); 

    } 

}

Output:

3 2

Time Complexity: O(N * M * log K)

Auxiliary Space: O(N * M)