[C++] - Beats 100% | Divide & Conquer | Explanation :)
Intuition\nThere\'s 2 problems here:\n1. efficiently calculating xor without repeating calculations\n2. selecting the k-th largest result without sorting\n\n1 -
# Intuition\nThere\'s 2 problems here:\n1. efficiently calculating xor without repeating calculations\n2. selecting the k-th largest result without sorting\n\n**1 - maintain matrix, 2 - quick select**\n\n\n\n# Approach\n1. Maintain matrix that keeps track of all xor of top-left sub matrix as suggested by hint.\n\n**Note:**\nUsing property of `^`, we see that `n ^ n = 0` where $n\\in\\mathcal{N}$. Principle of inclusion exclusion will reveal this relationship holds for our xor matrix:\n`xors[i][j] = xors[i - 1][j - 1] ^ xors[i][j - 1] ^ xors[i - 1][j] ^ matrix[i][j];`\n2. Followed by typical quick select.\n\n# Complexity\n- Time complexity: $\\mathcal{O}(n)$\n- Space complexity: $\\mathcal{O}(n)$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int kthLargestValue(vector<vector<int>>& matrix, int k) {\n        int m = matrix.size(), n = matrix[0].size();\n        vector<vector<int>> xors(m, vector<int>(n));\n        xors[0][0] = matrix[0][0];\n\n        // initialize xor matrix\n        int curr{};\n        vector<int> v{};\n        for (int i{}; i < m; ++i) {\n            curr ^= matrix[i][0];\n            xors[i][0] = curr;\n            v.push_back(curr);\n        }\n        for (int j{1}; j < n; ++j) {\n            xors[0][j] = xors[0][j - 1] ^ matrix[0][j];\n            v.push_back(xors[0][j]);\n        }\n\n        // populate matrix\n        for (int i{1}; i < m; ++i) {\n            for (int j{1}; j < n; ++j) {\n                xors[i][j] = xors[i - 1][j - 1] ^ xors[i][j - 1] ^ xors[i - 1][j] ^ matrix[i][j];\n                v.push_back(xors[i][j]);\n            }\n        }\n        return qs(v, k);\n    }\n\n    int qs(vector<int>& v, int k) {\n        vector<int> low, mid, high;\n        \n        int piv = v[v.size() / 2];\n        for (auto& n : v) {\n            if (n < piv) {\n                low.push_back(n);\n            } else if (n > piv) {\n                high.push_back(n);\n            } else {\n                mid.push_back(n);\n            }\n        }\n\n        // divide & conquer\n        if (k <= high.size()) {\n            return qs(high, k);\n        } else if (k <= high.size() + mid.size()) {\n            return piv;\n        } else {\n            return qs(low, k - high.size() - mid.size());\n        }\n    }\n};\n```
['Divide and Conquer', 'Quickselect', 'C++']