Find Kth Largest XOR Coordinate Value

1738. Find Kth Largest XOR Coordinate Value

class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        int h = matrix.size(), w = matrix[0].size();
        vector<vector<int>> dp(h, vector<int>(w, 0));
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < w; ++i) {
            dp[0][i] = dp[0][i - 1] ^ matrix[0][i];
        }
        for (int i = 1; i < h; ++i) {
            dp[i][0] = dp[i - 1][0] ^ matrix[i][0];
        }
        for (int i = 1; i < h; ++i) {
            for (int j = 1; j < w; ++j) {
                dp[i][j] = dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1] ^ matrix[i][j];
            }
        }

        priority_queue<int, vector<int>, greater<int>> pq;
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if (k) {
                    pq.push(dp[i][j]);
                    --k;
                } else if (pq.top() < dp[i][j]) {
                    pq.pop();
                    pq.push(dp[i][j]);
                }
            }
        }
        return pq.top();
    }
};

각 축의 0번 인덱스를 prefix xor 해 놓는다.
테이블의 i - 1/j - 1 인덱스의 값을 xor 한뒤 중복 xor 된 값을 살리기 위해 테이블의 i - 1, j - 1 값을 xor 해 준다. 그리고 maxtrix 의 i, j 값을 xor 해 주면 i, j 인덱스 에서 0..i, 0..j 모두 xor 한 값 을 구할 수 있다.
즉 prefix xor matrix 가 만들어 진다.

여기서 n 번째로 큰 값을 구하기 위해 테이블을 모두 순회하면서 최대크기 k 인 min heap 을 사용하여 top 이 테이블의 값보다 작으면 top 을 빼고 테이블의 값을 큐에 넣는다.
모두 순회 한 뒤, min heap 의 top 이 답이 된다.

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

• 테이블 생성 하는데, n·m + 테이블 모두 순회 n·m * 최대 크기 k 큐 push/pop log(k)

Space: O(n·m)

• prefix xor table size n·m + min heap size k