Problem

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 kth largest value (1-indexed) of all the coordinates of matrix.

Examples

Example 1

1
2
3

Input: matrix = [[5,2],[1,6]], k = 1
Output: 7
Explanation: The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.

Example 2

1
2
3

Input: matrix = [[5,2],[1,6]], k = 2
Output: 5
Explanation: The value of coordinate (0,0) is 5 = 5, which is the 2nd largest value.

Example 3

1
2
3

Input: matrix = [[5,2],[1,6]], k = 3
Output: 4
Explanation: The value of coordinate (1,0) is 5 XOR 1 = 4, which is the 3rd largest value.

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 1000
  • 0 <= matrix[i][j] <= 10^6
  • 1 <= k <= m * n

Solution

Method 1 – Prefix XOR and Heap/Sort

Intuition

We compute the XOR for each coordinate using prefix XOR, similar to prefix sum but with XOR. Then, we collect all values and find the kth largest using a heap or sorting.

Approach

  1. Create a 2D array pre where pre[i][j] is the XOR of all elements from (0,0) to (i,j).
  2. For each cell, compute pre[i][j] = matrix[i][j] ^ pre[i-1][j] ^ pre[i][j-1] ^ pre[i-1][j-1] (handle boundaries).
  3. Collect all pre[i][j] values into a list.
  4. Sort the list in descending order or use a min-heap of size k.
  5. Return the kth largest value.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    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> vals;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                pre[i][j] = matrix[i-1][j-1] ^ pre[i-1][j] ^ pre[i][j-1] ^ pre[i-1][j-1];
                vals.push_back(pre[i][j]);
            }
        }
        nth_element(vals.begin(), vals.begin() + k - 1, vals.end(), greater<int>());
        return vals[k-1];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func kthLargestValue(matrix [][]int, k int) int {
    m, n := len(matrix), len(matrix[0])
    pre := make([][]int, m+1)
    for i := range pre {
        pre[i] = make([]int, n+1)
    }
    vals := []int{}
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            pre[i][j] = matrix[i-1][j-1] ^ pre[i-1][j] ^ pre[i][j-1] ^ pre[i-1][j-1]
            vals = append(vals, pre[i][j])
        }
    }
    sort.Slice(vals, func(i, j int) bool { return vals[i] > vals[j] })
    return vals[k-1]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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];
        List<Integer> vals = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                pre[i][j] = matrix[i-1][j-1] ^ pre[i-1][j] ^ pre[i][j-1] ^ pre[i-1][j-1];
                vals.add(pre[i][j]);
            }
        }
        vals.sort(Collections.reverseOrder());
        return vals.get(k-1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun kthLargestValue(matrix: Array<IntArray>, k: Int): Int {
        val m = matrix.size; val n = matrix[0].size
        val pre = Array(m+1) { IntArray(n+1) }
        val vals = mutableListOf<Int>()
        for (i in 1..m) {
            for (j in 1..n) {
                pre[i][j] = matrix[i-1][j-1] xor pre[i-1][j] xor pre[i][j-1] xor pre[i-1][j-1]
                vals.add(pre[i][j])
            }
        }
        vals.sortDescending()
        return vals[k-1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def kthLargestValue(self, matrix: list[list[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])
        pre = [[0]*(n+1) for _ in range(m+1)]
        vals = []
        for i in range(1, m+1):
            for j in range(1, n+1):
                pre[i][j] = matrix[i-1][j-1] ^ pre[i-1][j] ^ pre[i][j-1] ^ pre[i-1][j-1]
                vals.append(pre[i][j])
        vals.sort(reverse=True)
        return vals[k-1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn kth_largest_value(matrix: Vec<Vec<i32>>, k: i32) -> i32 {
        let m = matrix.len();
        let n = matrix[0].len();
        let mut pre = vec![vec![0; n+1]; m+1];
        let mut vals = Vec::new();
        for i in 1..=m {
            for j in 1..=n {
                pre[i][j] = matrix[i-1][j-1] ^ pre[i-1][j] ^ pre[i][j-1] ^ pre[i-1][j-1];
                vals.push(pre[i][j]);
            }
        }
        vals.sort_unstable_by(|a, b| b.cmp(a));
        vals[(k-1) as usize]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

Complexity

  • ⏰ Time complexity: O(m * n + m * n * log(m * n)), for prefix computation and sorting all values.
  • 🧺 Space complexity: O(m * n), for storing prefix XORs and all values.