✅ QuickSelect Solution Explained | O(n*m) | 🥇Beats 100%
\n\n# Complexity\n- Time complexity: O(nm)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(nm)\n Add your space complexity here, e.g. O(n) 
![image.png](https://assets.leetcode.com/users/images/e8c2bf4c-d718-492e-a2b1-af5ff57cb7f4_1729329123.6839106.png)\n\n# Complexity\n- Time complexity: $$O(n*m)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n*m)$$\n<!-- Add your space complexity here, e.g. $$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        int n = matrix[0].size();\n        vector<int> nums;\n        nums.push_back(matrix[0][0]); \n\n        // create xor scores\n        for(int i = 0; i < m; i++) {\n            for(int j = 0; j < n; j++) {\n                if(i == 0 && j == 0) continue;\n                if(i == 0) {\n                    matrix[i][j] ^= matrix[i][j-1];\n                } else if(j == 0) {\n                    matrix[i][j] ^= matrix[i-1][j];\n                } else {\n                    matrix[i][j] ^= matrix[i-1][j] ^ matrix[i][j-1] ^ matrix[i-1][j-1];\n                }\n                nums.push_back(matrix[i][j]);\n            }\n        }\n\n        // kth largest element using quick select\n        return quickSelect(nums, 0, nums.size(), k);\n    }\n\n    int quickSelect(vector<int> &nums, int l, int r, int &k) {\n        while (l < r) {\n            // partition returns the boundary of subarray where values are equal to pivot element\n            auto [x, y] = partition(nums, l, r);\n\n            // if k lies between x and y then return value of elements between x and y (all have same value)\n            if (x < k && k <= y) return nums[x];\n\n            // if k lies to the left of boundary `y` search at the left of `x`\n            if (y > k) r = x;\n\n            // else search to the right of `y`\n            else l = y;\n        }\n\n        // return pivot value\n        return nums[l];     \n    }\n\n    pair<int, int> partition(vector <int> &a, int l, int r) {\n        int x = a[rand() % (r - l) + l];    // randomized pivot\n        int i = l, j = l, k = r - 1;    \n        // i = where to place elements greater than pivot\n        // k = where to place elements smaller than pivot\n        // j = current element under quesiton\n        \n        while (j <= k) {\n            if (a[j] > x) swap(a[j++], a[i++]);     // swap with left boundary element\n            else if (a[j] < x) swap(a[j], a[k--]);  // swap with right boundary element\n            else j++;                               // check next element without any swap\n        }\n\n        // return boundary of elements equal to pivot\n        return {i, j};\n    }\n};\n\n```
['Array', 'Divide and Conquer', 'Bit Manipulation', 'Matrix', 'Quickselect', 'C++']