[Python 3] Prefix-"XOR" and Quickselect (but why built-in sort() is faster?)
Intuition\n1. The problem essentially want us to find a largest Kth number out of a 2d matrix.\n2. This 2d matrix can be computed fastly using prefix-sum like m
###  Intuition\n1. The problem essentially want us to find a largest Kth number out of a 2d matrix.\n2. This 2d matrix can be computed fastly using prefix-sum like method.\n3. After we get the 2d matrix we want to search into, we can flatten it into a 1d array, and use quickselect.\n\n### Notice\n1. Like prefix-sum, for prefix-XOR matrix position `[i][j]`, we want to combine its previous row result and previous column result and remove the part that counted twice (prefix-XOR matrix `[i-1][j-1]`).\n2. Unlike prefix-sum, combining previous result is by XOR `^`, and remove previous result is also by XOR `^`. So we will just XOR matrix`[i][j]`, prefix-XOR`[i-1][j]`, prefix-XOR`[i][j-1]` and prefix-XOR`[i-1][j-1]` to get prefix-XOR`[i][j]`\n\n### BUT, quickselect does not seem to be working. Built-in sorted() works :(\n1. To get the largest Kth value of an array, we know that quickselect gives average O(n) time and worst case O(n^2) time. If we choose the pivot randomly, we can largely avoid O(n^2) scenario. But here using random pivot quickselect will TLE, but using built-in sort function which probably takes O(nlogn) time can beat 98% of runtime. **This does not make sense to me**, maybe sorted() is optimized enough and my own implementation of quickselect is a shit.\n```\nclass Solution:\n    def quickselect(self, arr, k, low, high):\n        """\n        select k largest element\n        """\n        def swap(arr, i, j):\n            arr[i], arr[j] = arr[j], arr[i]\n\n        def partition(arr, low, high):\n            """\n            select last elem as pivot, return the pivot index after rearranged array\n            """\n            # randomly choose index\n            randidx = random.randint(low,high)\n            pivot = arr[randidx]\n            swap(arr, randidx, high)\n\n            i = low\n            for j in range(low, high):\n                if arr[j] > pivot:\n                    swap(arr, i, j)\n                    i += 1\n\n            swap(arr, i, high)\n            return i\n        \n        if low == high:\n            return arr[low]\n\n        pivot_idx = partition(arr, low, high)\n\n        if k-1 == pivot_idx:\n            return arr[pivot_idx]\n        elif k-1 > pivot_idx: \n            return self.quickselect(arr, k, pivot_idx+1, high)\n        else:\n            return self.quickselect(arr, k, low, pivot_idx-1)\n\n        return quickselect(nums, k, 0, len(nums)-1)\n    \n    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n        """\n        prefix-XOR\n        flatten matrix into 1d\n        quickselect(k)\n        [ ][-][+][ ]\n        [ ][+][x][ ]\n        [ ][ ][ ][ ]\n        [ ][ ][ ][ ]\n        """\n        nrow, ncol = len(matrix), len(matrix[0])\n        prefix_XOR = [[0 for _ in range(ncol)] for _ in range(nrow)] \n        \n        # init first row and first col\n        prefix_XOR[0][0] = matrix[0][0]\n        for i in range(1,ncol):\n            prefix_XOR[0][i] = prefix_XOR[0][i-1] ^ matrix[0][i]\n        for i in range(1,nrow):\n            prefix_XOR[i][0] = prefix_XOR[i-1][0] ^ matrix[i][0]\n        # prefix XOR\n        for i in range(1,nrow):\n            for j in range(1,ncol):\n                prefix_XOR[i][j] = matrix[i][j] ^ prefix_XOR[i-1][j] ^ prefix_XOR[i][j-1] ^ prefix_XOR[i-1][j-1]\n                \n        # flatten 2d matrix into 1d\n        flatten = []\n        for i in prefix_XOR:\n            flatten += i\n            \n        # quick select k\n        # res = self.quickselect(flatten, k, 0, len(flatten)-1) # why quickselect not working? (TLE)\n        res = sorted(flatten)[-k] # why built-in sorted() works?\n        \n        return res\n        \n        \n```
['Quickselect', 'Python', 'Python3']