Mid/SeniorArrayBit ManipulationDivide and ConquerHeap (Priority Queue)MatrixPrefix SumQuickselectSorting
Find Kth Largest XOR Coordinate Value
You are given a 2D matrix of size m x n, consisting of non-negative integers. You are also given an integer k.
The value of coordinate (a, b) of the matrix is the XOR of all matrix[i][j] where 0 <= i <= a < m and 0 <= j <= b < n (0-indexed).
Find the k^th largest value (1-indexed) of all the coordinates of matrix.
Example 1
5 2 1 6
Input
matrix = [[5,2],[1,6]], k = 1Output
7The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.
Example 2
5 2 1 6
Input
matrix = [[5,2],[1,6]], k = 2Output
5The value of coordinate (0,0) is 5 = 5, which is the 2nd largest value.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 1000
- 0 <= matrix[i][j] <= 10^6
- 1 <= k <= m * n