Quick-select the k-th element, after computing the XOR-sum matrix using DP
Intuition\nQuick-select the k-th largest element, after computing the XOR-sum matrix using DP\n\n# Approach\ncompute the xor-sums using DP in place,\nthen quick
# Intuition\nQuick-select the k-th largest element, after computing the XOR-sum matrix using DP\n\n# Approach\ncompute the xor-sums using DP in place,\nthen quick-select the k-th largest value using kth_element(),\nwhich is O(n) on average.\n\nUse the std::greater<> comparator together with nth_element(),\nto make it very natural.\n\n# Complexity\n- Time complexity:\nO(N), where N = Rows * Cols.\n\n- Space complexity:\nO(N), where N = Rows * Cols.\n\n# Code\n```cpp [C++]\n// Idea: compute the xor-sums using DP,\n// then quick-select the k-th largest value using kth_element().\n// Complexity: O(N), where N = Rows * Cols.\nclass Solution {\npublic:\n    int kthLargestValue(vector<vector<int>>& matrix, int k) {\n        const int nr = matrix.size();\n        const int nc = matrix[0].size();\n        vector<int> v;\n        v.reserve(nr * nc);\n        // compute the xor-sums using DP,\n        for (int r = 0; r < nr; ++r) {\n            auto& row = matrix[r];\n            // sum is the xor-sum of the current prefix of the current row\n            for (int c = 0, sum = 0; c < nc; ++c) {\n                sum ^= row[c];\n                if (r == 0) {\n                    row[c] = sum;\n                } else {\n                    row[c] = matrix[r - 1][c] ^ sum;\n                }\n                v.emplace_back(row[c]);\n            }\n        }\n        // quick-select the k-th largest value using kth_element().\n        // O(N) on average\n        nth_element(v.begin(), v.begin() + k - 1, v.end(), greater<>{});\n        return *(v.begin() + k - 1);\n    }\n};\n```\n
['Dynamic Programming', 'Quickselect', 'C++']