[Python3] compute xor O(MNlog(MN)) | O(MNlogK) | O(MN)
Algo\nCompute xor of at (i, j) as xor[i][j] = xor[i-1][j] ^ xor[i][j-1] ^ xor[i-1][j-1] ^ matrix[i][j]. The return the kth largest among observed. \n\nImplement
**Algo**\nCompute `xor` of at `(i, j)` as `xor[i][j] = xor[i-1][j] ^ xor[i][j-1] ^ xor[i-1][j-1] ^ matrix[i][j]`. The return the `k`th largest among observed. \n\n**Implementation**\n```\nclass Solution:\n    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n        m, n = len(matrix), len(matrix[0]) # dimensions \n        \n        ans = []\n        for i in range(m): \n            for j in range(n): \n                if i: matrix[i][j] ^= matrix[i-1][j]\n                if j: matrix[i][j] ^= matrix[i][j-1]\n                if i and j: matrix[i][j] ^= matrix[i-1][j-1]\n                ans.append(matrix[i][j])\n        return sorted(ans)[-k] \n```\n\n**Analysis**\nTime complexity `O(MNlog(MN))` (`O(MN)` is possible via quick select)\nSpace complexity `O(MN)`\n\nEdited on 1/24/2021\nAdding two more implementation for improved time complexity \n`O(MNlogK)` time & `logK` space \n```\nclass Solution:\n    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n        m, n = len(matrix), len(matrix[0]) # dimensions \n        \n        pq = []\n        for i in range(m): \n            for j in range(n): \n                if i: matrix[i][j] ^= matrix[i-1][j]\n                if j: matrix[i][j] ^= matrix[i][j-1]\n                if i and j: matrix[i][j] ^= matrix[i-1][j-1]\n                heappush(pq, matrix[i][j])\n                if len(pq) > k: heappop(pq)\n        return pq[0]\n```\n\n\n`O(MN)` time & `O(MN)` space \n```\nclass Solution:\n    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n        m, n = len(matrix), len(matrix[0]) # dimensions \n        \n        vals = []\n        for i in range(m): \n            for j in range(n): \n                if i: matrix[i][j] ^= matrix[i-1][j]\n                if j: matrix[i][j] ^= matrix[i][j-1]\n                if i and j: matrix[i][j] ^= matrix[i-1][j-1]\n                vals.append(matrix[i][j])\n        \n        def part(lo, hi): \n            """Partition vals from lo (inclusive) to hi (exclusive)."""\n            i, j = lo+1, hi-1\n            while i <= j: \n                if vals[i] < vals[lo]: i += 1\n                elif vals[lo] < vals[j]: j -= 1\n                else: \n                    vals[i], vals[j] = vals[j], vals[i]\n                    i += 1\n                    j -= 1\n            vals[lo], vals[j] = vals[j], vals[lo]\n            return j \n        \n        lo, hi = 0, len(vals)\n        while lo < hi: \n            mid = part(lo, hi)\n            if mid + k < len(vals): lo = mid + 1\n            else: hi = mid\n        return vals[lo]\n```
['Python3']