Python3 | DP + QuickSelect | Easy to understand
Intuition\n Describe your first thoughts on how to solve this problem. \nLet\'s construct all possible xors list and use quick select to find the Kth largest va
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet\'s construct all possible xors list and use quick select to find the Kth largest value.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirstly I tried brute-forcing the matrix to calculate the i, j xor - solution did not pass. Then I tried using DP and the solution passed.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(m*n): DP is always m*n and quick select\'s worst case is m*n.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m*n): quick select\'s additional lists.\n# Code\n```\nfrom random import choice\nclass Solution:\n    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:\n        xors = self.construct_xors(matrix)\n        return self.quick_select(xors, k)\n\n    def construct_xors(self, xors):\n        m = len(xors)\n        n = len(xors[0])\n\n        def valid_coord(i, j):\n            return 0 <= i < m and 0 <= j < n\n\n        for i in range(m):\n            for j in range(n):\n                for di, dj in ((-1, 0), (0, -1), (-1, -1)):\n                    ci, cj = i + di, j + dj\n                    xors[i][j] ^= xors[ci][cj] * valid_coord(ci, cj)\n    \n        xors = [xor for row in xors for xor in row]\n        return xors\n\n    def quick_select(self, container, k):\n        pivot = choice(container)\n\n        g = [xor for xor in container if xor > pivot]\n        e = [xor for xor in container if xor == pivot]\n        l = [xor for xor in container if xor < pivot]\n\n        if len(g) > k:\n            return self.quick_select(g, k)\n        if len(g) == k:\n            return min(g)\n        if len(g) + len(e) >= k:\n            return e[0]\n        if len(g) + len(e) + len(l) > k:\n            return self.quick_select(l, k - len(g) - len(e))\n        if len(g) + len(e) + len(l) == k:\n            return min(l)\n\n```
['Dynamic Programming', 'Quickselect', 'Python3']