1738. Find Kth Largest XOR Coordinate Value #

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.

Example 1:

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:

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:

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.

Example 4:

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

Constraints:

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

Problem Statement #

Given a 2D matrix matrix and an integer k, where the matrix has size m x n and consists of non-negative integers. The value of coordinate (a, b) in the matrix is obtained by performing XOR on all elements matrix[i][j] that satisfy 0 <= i <= a < m and 0 <= j <= b < n (0-indexed). Please find the kth largest value among all coordinates of matrix (where k is 1-indexed).

Solution Ideas #

The interval XOR result is analogous to a 2D prefix sum over an interval. The only thing to note is the property that x^x = 0. For example:
Through simple reasoning, we can derive the recurrence formula for the 2D prefix sum preSum. See Solution 2 for the specific code.
In the solution above, preSum is computed with a 2D array. Can the space complexity be further optimized and reduced to O(n)? The answer is yes. By observation, we can find that preSum can be generated row by row. First generate the previous row of preSum; when generating the next row, information from the previous row will be used. After the XOR calculation, the original data (the information from the previous row) can be overwritten, which has no impact on subsequent calculations. This method of optimizing space complexity is exactly the same idea and method as optimizing DP space complexity.
See Solution 1 for the specific code.
After computing preSum, we also need to consider how to output the kth largest value. There are 3 approaches: the first is sorting, the second is a priority queue, and the third is the O(n) partition method from Problem 215. The one with the lowest time complexity is of course O(n). However, after actual testing, the sorting method has the best runtime. Therefore, both methods below use sorting.

Code #

package leetcode

import "sort"

// Solution 1: compressed prefix sum
func kthLargestValue(matrix [][]int, k int) int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return 0
	}
	res, prefixSum := make([]int, 0, len(matrix)*len(matrix[0])), make([]int, len(matrix[0]))
	for i := range matrix {
		line := 0
		for j, v := range matrix[i] {
			line ^= v
			prefixSum[j] ^= line
			res = append(res, prefixSum[j])
		}
	}
	sort.Ints(res)
	return res[len(res)-k]
}

// Solution 2: prefix sum
func kthLargestValue1(matrix [][]int, k int) int {
	nums, prefixSum := []int{}, make([][]int, len(matrix)+1)
	prefixSum[0] = make([]int, len(matrix[0])+1)
	for i, row := range matrix {
		prefixSum[i+1] = make([]int, len(matrix[0])+1)
		for j, val := range row {
			prefixSum[i+1][j+1] = prefixSum[i+1][j] ^ prefixSum[i][j+1] ^ prefixSum[i][j] ^ val
			nums = append(nums, prefixSum[i+1][j+1])
		}
	}
	sort.Ints(nums)
	return nums[len(nums)-k]
}