Find Kth Largest XOR Coordinate Value

medium matrix prefix sum bit manipulation

Problem

You are given an m × n matrix. The XOR coordinate value at position (a, b) is the XOR of every element matrix[i][j] with i ≤ a and j ≤ b — that is, the XOR of the whole rectangle from the top-left corner down to (a, b). There are m × n such coordinate values. Given an integer k, return the kth largest of all these values.

Inputmatrix = [[5,2],[1,6]], k = 1

Output7

The four coordinate values are 5, 7, 4, 0. Sorted from largest they are 7, 5, 4, 0, so the 1st largest is 7.

matrix (JSON matrix)

def kth_largest_value(matrix, k):
    m, n = len(matrix), len(matrix[0])
    pre = [[0] * (n + 1) for _ in range(m + 1)]
    values = []
    for i in range(m):
        for j in range(n):
            pre[i + 1][j + 1] = matrix[i][j] ^ pre[i][j + 1] ^ pre[i + 1][j] ^ pre[i][j]
            values.append(pre[i + 1][j + 1])
    values.sort(reverse=True)
    return values[k - 1]

function kthLargestValue(matrix, k) {
  const m = matrix.length, n = matrix[0].length;
  const pre = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  const values = [];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      pre[i + 1][j + 1] = matrix[i][j] ^ pre[i][j + 1] ^ pre[i + 1][j] ^ pre[i][j];
      values.push(pre[i + 1][j + 1]);
    }
  }
  values.sort((a, b) => b - a);
  return values[k - 1];
}

class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int[][] pre = new int[m + 1][n + 1];
        int[] values = new int[m * n];
        int idx = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                pre[i + 1][j + 1] = matrix[i][j] ^ pre[i][j + 1] ^ pre[i + 1][j] ^ pre[i][j];
                values[idx++] = pre[i + 1][j + 1];
            }
        }
        Arrays.sort(values);
        return values[m * n - k];
    }
}

int kthLargestValue(vector<vector<int>>& matrix, int k) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> pre(m + 1, vector<int>(n + 1, 0));
    vector<int> values;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            pre[i + 1][j + 1] = matrix[i][j] ^ pre[i][j + 1] ^ pre[i + 1][j] ^ pre[i][j];
            values.push_back(pre[i + 1][j + 1]);
        }
    }
    sort(values.rbegin(), values.rend());
    return values[k - 1];
}

Explanation

The naive approach would re-XOR every cell of the top-left rectangle for each of the m × n coordinates, which repeats a lot of work. Instead we build a 2D XOR prefix grid once, where pre[i+1][j+1] already holds the XOR of the whole rectangle from (0,0) down to (i,j). That is exactly the coordinate value at (i,j).

Each prefix cell is filled with matrix[i][j] ^ pre[i][j+1] ^ pre[i+1][j] ^ pre[i][j]. This is the same inclusion-exclusion shape used for ordinary 2D prefix sums, except addition and subtraction are both replaced by XOR. We combine the strip above and the strip to the left, then XOR back the top-left overlap — under XOR, applying a value twice cancels it, so the doubly-counted corner is removed.

As we compute each prefix cell we drop its value into a list. After the grid is built, that list holds all m × n coordinate values. We sort them from largest to smallest and read off the value at index k − 1, the kth largest.

Example: matrix = [[5,2],[1,6]]. The prefix cells come out as pre[1][1] = 5, pre[1][2] = 2 ^ 5 = 7, pre[2][1] = 1 ^ 5 = 4, and pre[2][2] = 6 ^ 7 ^ 4 ^ 5 = 0. The coordinate values are 5, 7, 4, 0; sorted from largest they are 7, 5, 4, 0, so for k = 1 the answer is 7.

Time: O(m · n · log(m · n)) Space: O(m · n)