1738. Find Kth Largest XOR Coordinate Value

LeetCode 1738. Find Kth Largest XOR Coordinate Value

Description

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] <= 106

• 1 <= k <= m * n

Tags

Array

Solution

1. Compute 2D prefix-xor;

2. Reshape it to 1D array and get the largest Kth element.

Complexity

• Time complexity: $O(mn\log(mn))$

• Space complexity: $O(mn)$

Code

func kthLargestValue(matrix [][]int, k int) int {
	results, pre := make([]int, 0, len(matrix)*len(matrix[0])), make([][]int, len(matrix)+1)
	pre[0] = make([]int, len(matrix[0])+1)
	for i, row := range matrix {
		pre[i+1] = make([]int, len(matrix[0])+1)
		for j, val := range row {
			pre[i+1][j+1] = pre[i+1][j] ^ pre[i][j+1] ^ pre[i][j] ^ val
			results = append(results, pre[i+1][j+1])
		}
	}
	sort.Sort(sort.Reverse(sort.IntSlice(results)))
	return results[k-1]
}

Reference

1. 找出第 K 大的异或坐标值