Skip to content

1738. Find Kth Largest XOR Coordinate Value 👍

  • Time: $O(mn\log k)$
  • Space: $O(mn + k)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int kthLargestValue(vector<vector<int>>& matrix, int k) {
    const int m = matrix.size();
    const int n = matrix[0].size();
    vector<vector<int>> xors(m + 1, vector<int>(n + 1));
    priority_queue<int, vector<int>, greater<>> minHeap;

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j) {
        xors[i][j] = xors[i - 1][j] ^ xors[i][j - 1] ^ xors[i - 1][j - 1] ^
                     matrix[i - 1][j - 1];
        minHeap.push(xors[i][j]);
        if (minHeap.size() > k)
          minHeap.pop();
      }

    return minHeap.top();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int kthLargestValue(int[][] matrix, int k) {
    final int m = matrix.length;
    final int n = matrix[0].length;
    int[][] xors = new int[m + 1][n + 1];
    Queue<Integer> minHeap = new PriorityQueue<>();

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j) {
        xors[i][j] = xors[i - 1][j] ^ xors[i][j - 1] ^ xors[i - 1][j - 1] ^ matrix[i - 1][j - 1];
        minHeap.offer(xors[i][j]);
        if (minHeap.size() > k)
          minHeap.poll();
      }

    return minHeap.peek();
  }
}