[Python] Prefix XOR Array
Approach:\n\nWe can compute the xor value of matrix[0:i][0:j] for all matrix[i][j] in \nO(MN) time through the following trick.\n\nmatrix[i][j] = matrix[i][j]^m
**Approach:**\n\nWe can compute the xor value of matrix[0:i][0:j] for all matrix[i][j] in \nO(MN) time through the following trick.\n\n```matrix[i][j] = matrix[i][j]^matrix[i-1][j-1]^matrix[i-1][j]^matrix[i][j-1]```\n\nThen it\'s just a matter of finding the K<sup>th</sup> largest value in the array.\n\nSort the values in the array and return arr[-k]\n\n<details>\n\n<summary><b>Intuition:</b> (click to show)</summary>\n\nThis trick is derived from the prefix sum shortcut for 2d arrays.\n\n```matrix[i][j] += matrix[i][j-1] + matrix[i-1][j] - matrix[i-1][j-1]```\n\nThe difference here is that we are dealing with xor instead of summation.\n\nSince a^b equals b^a the equivalent formula for xors is simply:\n\n```matrix[i][j] ^= matrix[i][j-1]^matrix[i-1][j]^matrix[i-1][j-1]```\n\n</details>\n\n<br>\n\n```python\ndef kthLargestValue(self, matrix: List[List[int]], K: int) -> int:\n\tR, C = len(matrix), len(matrix[0])\n\tarr = []\n\tfor i in range(R):\n\t\tfor j in range(C):\n\t\t\tif i and j:\n\t\t\t\tmatrix[i][j] ^= matrix[i-1][j]^matrix[i][j-1]^matrix[i-1][j-1]\n\t\t\telif i:\n\t\t\t\tmatrix[i][j] ^= matrix[i-1][j]\n\t\t\telif j:\n\t\t\t\tmatrix[i][j] ^= matrix[i][j-1]\n\t\t\tarr.append(matrix[i][j])\n\tarr.sort()\n\treturn arr[-K]\n```
[]