Priority Queues? What for? 176 ms and 100% Win in C++ using Count Sort.
Intuition\nWe are given an $n \times m$ matrix, and we need to calculate the $k$-th maximum of submatrix XOR values where a submatrix for $i, j$ begins at $0, 0
# Intuition\nWe are given an $n \\times m$ matrix, and we need to calculate the $k$-th maximum of submatrix XOR values where a submatrix for $i, j$ begins at $0, 0$ and ends at $i, j$ inclusively, for each $0 < i < n; 0 < j < m$.\n\nConstraints:\n* $1 <= n, m <= 1000$\n* $0 <= element < 10^6$\n* $1 <= k < m \\times n$\n\nThe submatrix calculation can be done in one pass ($O(n \\times m)$). Most solutions utilize additional storage of the matrix size, but in fact it is redundant - we can XOR the original matrix in place using the formula $M_{i,j} = M_{i,j-1} \\oplus M_{i-1,j} \\oplus M_{i-1,j-1}$. Each of $M_{i,j-1}$ and $M_{i-1,j}$ contains the submatrix $M_{i-1,j-1}$, so it\'s XORed twice, and we just include it one more time to ensure it participates in the sum.\n\nThen we need to choose the method of finding the $k$-th maximal value. There are at least three opportunities:\n1. Flatten the matrix and apply $O(n \\times m \\times log_2(k))$ partial sorting to it, then pick the element in $O(1)$ time. This requires either an additional storage for $O(n \\times m)$ elements or a custom iterator to view the existing 2D matrix as a flat 1D array. The first way requires additional $O(n \\times m)$ storage, and the second way is more complicated, yet not too hard, to implement.\nThe matrix traversal does not imply an additional cost (since we are traversing it anyway to calculate XORs), so the time complexity of this approach would be $O(n \\times m \\times log(k))$.\n1. Add elements to a min-heap priority queue (this can be done during the first matrix traversal where we calculate XORs), limiting its size to $k$, then pick the top element from it. There would be $0$, $1$ or $2$ modifications to the heap for each element (depending the current queue size and the relationship between the current element and the top element of the heap), each requiring $O(log(k))$ element movements. This approach is favoured in majority of solutions here. Its time complexity is also $O(n \\times m \\times log(k))$. It requires an $O(k)$ additional space.\n1. Use Count Sort: accumulate element frequencies in an $O(r)$ array, where $r$ is the value range, then iterate through it calculating a running sum of frequencies until it reaches $k$. The time complexity of this approach is $O(n \\times m + r)$ in worst case and $O(n \\times m + k)$ on average.\n\n# Approach\n\nConsidering that $k$ is comparable to $n \\times m$, we first try the approach (3) - it does not have a logarithmic multiplier for time, it requires a similar amount of space to (2), and it\'s not as complex as a custom iterator in (1).\n\nFirst of all we need to calculate XORs and register them in our frequencies array. As we calculate XORs, we also maintain minimal and maximal XOR values which would be the iteration boundaries for finding the $k$-th maximum.\n\nOnce frequencies are gathered, we add them up starting from the largest element until the sum reaches $k$. The element at which the iteration stops is our $k$-th maximum, only we need to increase it by $1$ to compensate for the last decrement of the loop.\n\nFinally, we set all frequencies within the used range to zero, so the static array can be reused in the next test.\n\n# Complexity\n- Time complexity: $O(n \\times m + r)$.\n\n- Space complexity: $O(n \\times m + r)$ for the frequencies array.\n\n# Micro-optimizations\n\nThe frequencies array is allocated statically to the maximum possible size and cleaned with the used range after each test case.\n\nNormally the element size of the frequencies array should be at least 20 bit to hold values up to $max(n \\times m) = 1000000$, which means either a 32 bit integers per counter or a 64 bit integer per 3 counters. However it turned out that on the present LC\'s test suite, 16 bit is enough for a counter.\n\nThe XOR and frequency calculation loop is split in 4 parts:\n- The element at $0, 0$ is already final, so we just increment a counter for it.\n- $0$-th row and column are edge cases, we go through them in separate loops to avoid excessive branching within the main loop (things like `if (minv > v) minv = v;` don\'t count - compilers use to translate them to a branchless code).\n- Then we go through the main body of the matrix in $(n - 1) \\times (m - 1)$ iterations.\n\nO3 optimization is turned on and `stdio` sync is turned off, as usually (not included here for brevity).\n\n# Measurements\n\n| Language | Time | Beating | Memory | Beating |\n|-|-|-|-|-|\n| C++ | 176-198 ms | 100% | 89.1-89.2 Mb | 100% |\n\nSubmission links:\nhttps://leetcode.com/problems/find-kth-largest-xor-coordinate-value/submissions/1097823950/\nhttps://leetcode.com/problems/find-kth-largest-xor-coordinate-value/submissions/1097837453/\n\n# Code\n``` C++ []\nclass Solution {\nprivate:\n    typedef unsigned short dim_t;\n\n    static constexpr unsigned MAXV = 1000000u;\n    static constexpr unsigned FSIZE = MAXV + 1u;\n\n    static dim_t freqs[FSIZE];\n\npublic:\n    int kthLargestValue(vector<vector<int>>& matrix, int k) {\n        const dim_t n = matrix.size();\n        const dim_t m = matrix[0].size();\n        unsigned minv = matrix[0][0], maxv = minv;\n        freqs[maxv]++;\n        for (dim_t i = 1; i < n; i++) {\n            const unsigned v = matrix[i][0] ^= matrix[i - 1][0];\n            if (minv > v) minv = v;\n            if (maxv < v) maxv = v;\n            freqs[v]++;\n        }\n        for (dim_t j = 1; j < m; j++) {\n            const unsigned v = matrix[0][j] ^= matrix[0][j - 1];\n            if (minv > v) minv = v;\n            if (maxv < v) maxv = v;\n            freqs[v]++;\n        }\n        for (dim_t i = 1; i < n; i++)\n            for (dim_t j = 1; j < m; j++) {\n                const unsigned v = matrix[i][j] ^= matrix[i][j - 1] ^ matrix[i - 1][j] ^ matrix[i - 1][j - 1];\n                if (minv > v) minv = v;\n                if (maxv < v) maxv = v;\n                freqs[v]++;\n            }\n        unsigned v = maxv;\n        for (unsigned count = 0; count < k; v--)\n            count += freqs[v];\n        fill(freqs + minv, freqs + maxv + 1u, 0);\n        return v + 1u;\n    }\n};\n\nSolution::dim_t Solution::freqs[FSIZE];\n```
['Array', 'Bit Manipulation', 'Matrix', 'Counting Sort', 'C++']