Java | 2 methods | Explained
Idea: This problem is a combination of 2 problems:\n LC 304: Range Sum Query 2D - Immutable, followed by\n LC 215: Kth Largest Element in an Array.\n\nAfter fin
**Idea:** This problem is a combination of 2 problems:\n* [LC 304: Range Sum Query 2D - Immutable](https://leetcode.com/problems/range-sum-query-2d-immutable/discuss/1256376/Java-or-Fenwick-Tree), followed by\n* [LC 215: Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/1258054/Java-or-Quick-Select-or-Time-beats-100).\n\nAfter finding the prefix array from first step (LC 304), the problem reduces to finding the kth largest in that array (LC 215). Finding kth largest can be done in a lot of ways, the fastest being quick select. Quick Select\'s speed is also effected by the choice of pivot. More often than not, the [median of three technique](https://stackoverflow.com/questions/7559608/median-of-three-values-strategy) comes out to be the fastest with the least computational overhead (read random pivot).\n\n**Method 1:** Prefix XOR and Min Heap\n>**T/S:** O(mn lg k)/O(mn)\n```\npublic int kthLargestValueHeap(int[][] matrix, int k) {\n\tvar minHeap = new PriorityQueue<Integer>(k);\n\tvar prefixXor = new int[matrix.length + 1][matrix[0].length + 1];\n\t\n\tfor (var i = 1; i < prefixXor.length; i++)\n\t\tfor (var j = 1; j < prefixXor[0].length; j++) {\n\t\t\tprefixXor[i][j] = matrix[i - 1][j - 1]\n\t\t\t\t\t\t\t^ prefixXor[i - 1][j]\n\t\t\t\t\t\t\t^ prefixXor[i][j - 1]\n\t\t\t\t\t\t\t^ prefixXor[i - 1][j - 1];\n\t\t\tminHeap.add(prefixXor[i][j]);\n\t\t\tif (minHeap.size() > k)\n\t\t\t\tminHeap.poll();\n\t\t}\n\t\t\n\treturn minHeap.peek();\n}\n```\n\n**Method 2:** Prefix XOR and Quick Select\n>**T/S:** O(mn)/O(mn)\n\n```\npublic int kthLargestValue(int[][] matrix, int k) {\n\tvar m = matrix.length;\n\tvar n = matrix[0].length;\n\tvar prefixXor = new int[m + 1][n + 1];\n\tvar flattened = new int[m * n];\n\n\tfor (int t = 0, i = 1; i < m + 1; i++)\n\t\tfor (var j = 1; j < n + 1; j++) {\n\t\t\tprefixXor[i][j] = matrix[i - 1][j - 1]\n\t\t\t\t\t\t\t^ prefixXor[i - 1][j] // left neighbor\n\t\t\t\t\t\t\t^ prefixXor[i][j - 1] // top neighbor\n\t\t\t\t\t\t\t^ prefixXor[i - 1][j - 1]; // intersection of left and top neighbors\n\t\t\tflattened[t++] = prefixXor[i][j];\n\t\t}\n\n\tvar target = flattened.length - k;\n\tquickSelect(flattened, 0, flattened.length - 1, target);\n\treturn flattened[target];\n}\n\nprivate void quickSelect(int[] nums, int start, int end, int target) {\n\tif (start >= end)\n\t\treturn;\n\tvar i = start;\n\tvar j = end;\n\tvar pivot = getPivot(nums[start], nums[(start + end) / 2], nums[end]);\n\t// partition starts\n\twhile (i <= j) {\n\t\twhile (nums[i] < pivot)\n\t\t\ti++;\n\t\twhile (nums[j] > pivot)\n\t\t\tj--;\n\t\tif (i <= j)\n\t\t\tswap(nums, i++, j--);\n\t}\n\t// partition ends\n\tif (target < i)\n\t\tquickSelect(nums, start, i - 1, target);\n\telse\n\t\tquickSelect(nums, i, end, target);\n}\n\nprivate void swap(int[] nums, int i, int j) {\n\tvar temp = nums[i];\n\tnums[i] = nums[j];\n\tnums[j] = temp;\n}\n\nprivate int getPivot(int a, int b, int c) {\n\tvar triplet = new int[]{a, b, c};\n\tArrays.sort(triplet);\n\treturn triplet[1];\n}\n```\n***Please upvote if this helps***
['Quickselect', 'Java']