Find Kth Largest XOR Coordinate Value LeetCode solution in C++

1
class Solution {
2
 public:
3
  int kthLargestValue(vector<vector<int>> &matrix, int k) {
4
    int m = matrix.size(), n = matrix[0].size();
5

6
    vector<int> coordinates;
7
    vector<vector<int>> prefixXOR(m, vector<int>(n, 0));
8

9
    for (int i = 0; i < m; i++) {
10
      for (int j = 0; j < n; j++) {
11
        if (i == 0 && j == 0)
12
          prefixXOR[i][j] = matrix[0][0];
13
        else if (i == 0 && j != 0)
14
          prefixXOR[i][j] = prefixXOR[i][j - 1] ^ matrix[i][j];
15
        else if (i != 0 && j == 0)
16
          prefixXOR[i][j] = prefixXOR[i - 1][j] ^ matrix[i][j];
17
        else
18
          prefixXOR[i][j] =
19
              prefixXOR[i - 1][j] ^ prefixXOR[i][j - 1] ^ prefixXOR[i - 1][j - 1] ^ matrix[i][j];
20
      }
21
    }
22

23
    priority_queue<int, vector<int>, greater<int>> heap;
24

25
    for (int i = 0; i < m; i++) {
26
      for (int j = 0; j < n; j++) {
27
        if (heap.size() == k) {
28
          if (prefixXOR[i][j] > heap.top()) {
29
            heap.pop();
30
            heap.push(prefixXOR[i][j]);
31
          }
32
        } else
33
          heap.push(prefixXOR[i][j]);
34
      }
35
    }
36
    return heap.top();
37
  }
38
};