Description

Submission

class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();

        auto preXor = matrix;

        multiset<int>kLargest;

        for(int j = 1; j < n; ++j) {
            preXor[0][j] ^= preXor[0][j-1]; 
        }

        for(int i = 1; i < m; ++i) {
            preXor[i][0] ^= preXor[i-1][0];
        }

        for(int i = 1; i < m; ++i) {
            for(int j = 1; j < n; ++j) {
                preXor[i][j] ^= preXor[i-1][j-1] ^ preXor[i][j-1] ^ preXor[i-1][j];
            }
        }

        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                kLargest.insert(preXor[i][j]);
                if(kLargest.size() > k) {
                    kLargest.erase(kLargest.begin());
                }
            }
        }
        return *kLargest.begin();
    }
};

class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();

        auto preXor = matrix;

        priority_queue<int, vector<int>, greater<int>> kLargest;

        for(int j = 1; j < n; ++j) {
            preXor[0][j] ^= preXor[0][j-1]; 
        }

        for(int i = 1; i < m; ++i) {
            preXor[i][0] ^= preXor[i-1][0];
        }

        for(int i = 1; i < m; ++i) {
            for(int j = 1; j < n; ++j) {
                preXor[i][j] ^= preXor[i-1][j-1] ^ preXor[i][j-1] ^ preXor[i-1][j];
            }
        }

        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                kLargest.push(preXor[i][j]);
                if(kLargest.size() > k) {
                    kLargest.pop();
                }
            }
        }
        return kLargest.top();
    }
};

 class Solution {
    int m, n;
    vector<vector<int>> preXor;

    int count(int val) {
        int ret = 0;
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(preXor[i][j] >= val) ret++;
            }
        }
        return ret;
    }

public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        m = matrix.size();
        n = matrix[0].size();

        preXor = matrix;

        priority_queue<int, vector<int>, greater<int>> kLargest;

        for(int j = 1; j < n; ++j) {
            preXor[0][j] ^= preXor[0][j-1]; 
        }

        for(int i = 1; i < m; ++i) {
            preXor[i][0] ^= preXor[i-1][0];
        }

        for(int i = 1; i < m; ++i) {
            for(int j = 1; j < n; ++j) {
                preXor[i][j] ^= preXor[i-1][j-1] ^ preXor[i][j-1] ^ preXor[i-1][j];
            }
        }

        int left = 0, right = INT_MAX;

        while(left < right) {
            int mid = right - (right - left) / 2;
            if(count(mid) >= k) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};