This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 1738 on LeetCode. Finding the KTH xor coordinate is medium difficulty.

Tag: “Top K”, “math”, “prefix and”

You are given a two dimensional matrix matrix and an integer k of size m, x and n consisting of non-negative integers.

The values of the coordinates (a, b) in the matrix can be obtained by performing xOR on all elements of matrix[I][j] (counting subscripts from 0) such that 0 <= I <= a < m and 0 <= j <= b < n.

Please find the KTH largest value of all the coordinates of the matrix (the value of k is counted from 1).

Example 1:

Input: matrix = [[5,2],[1,6]], k = 1 output: 7 interpretation: the value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.Copy the code

Example 2:

Input: matrix = [[5,2],[1,6]], k = 2 output: 5 interpretation: the value of coordinate (0,0) is 5 = 5, which is the second largest value.Copy the code

Example 3:

Input: matrix = [[5,2],[1,6]], k = 3 Output: 4 Interpretation: the value of the coordinate (1,0) is 5 XOR 1 = 4, which is the third largest value.Copy the code

Example 4:

Input: matrix = [[5,2],[1,6]], k = 4 Output: 0 Interpretation: the value of coordinate (1,1) is 5 XOR 2 XOR 1 XOR 6 = 0, which is the fourth largest value.Copy the code

Tip:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 1000
  • 0 < =matrix[i][j]< =
    1 0 6 10 ^ 6
  • 1 <= k <= m * n

Fundamental analysis

The upper left end of all submatrices is (0,0)(0, 0)(0,0).

The data range is 10310^3103, so the naive method of “enumerating all lower-right corners” and “calculating the xor sum of submatrices each time” O(m2∗n2)O(m^2 * n^2)O(m2∗n2) is not considered.

To find the optimal in the global, the process of “enumerating all the lower right corner” is inevitable. We can optimize the process of “calculating the xOR sum of submatrix every time”.

This analysis process is similar to 1310. Subarray xor query.

Xor as a non-carry addition can be used with “even times xor results in
0 0 “Implements an exclusion similar to” prefix and “. This allows us to be in the
O ( 1 ) O(1) Calculate “xOR sum of some submatrix” in complexity.

Two dimensional prefix Xor & priority queue (heap)

Create a 2 d array sum [] [] sum [] [] sum [] [], the sum [I] [j] sum [I] [j] sum [I] [j] as to (I, j) (I, j) (I, j) to the lower right corner of xor and matrix, we may safely draw the formula:


s u m [ i ] [ j ] = s u m [ i – 1 ] [ j ] The radius s u m [ i ] [ j – 1 ] The radius s u m [ i – 1 ] [ j – 1 ] The radius m a t r i x [ i – 1 ] [ j – 1 ] Sum [I] [j] = sum [I – 1) [j] radius sum [I] [1] the radius sum [I – 1] [1] the radius matrix [I – 1] [1]

The remaining problem is to find the KTH largest value from all the “xor sum of submatrices”.

It becomes a Top K problem, which can be solved using sort or heap.

Specifically, we can build a small root heap with the size of KKK, and judge whether the current “sub-matrix xOR sum” is greater than the top element when calculating the two-dimensional prefix xor:

  • Greater than heap-top element: The xOR and of the current submatrix may be the largest value in KKK, and the heap-top element cannot be the largest value in KKK. Pops the top element of the heap and adds the current submatrix and to the heap
  • Elements less than the top of the heap: values that are not KKK large are discarded.
  • Is equal to the top of the heap: if the same element exists in the heap, it is discarded.

The final heap top element is the answer.

Code:

class Solution {
    public int kthLargestValue(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] sum = new int[m + 1][n + 1];
        PriorityQueue<Integer> q = new PriorityQueue<>(k, (a, b)->a - b);
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] ^ sum[i][j - 1] ^ sum[i - 1][j - 1] ^ mat[i - 1][j - 1];
                if (q.size() < k) {
                    q.add(sum[i][j]);
                } else {
                    if(sum[i][j] > q.peek()) { q.poll(); q.add(sum[i][j]); }}}}returnq.peek(); }}Copy the code
  • Time complexity: O(m∗n∗log⁡k)O(m * n * \log{k})O(m∗n∗logk)
  • Space complexity: O(m∗n)O(M * n)O(m∗n)

The last

This is the No.1738 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.