O(n): Segment tree
Perhaps overkill for this problem, but this is a great opportunity for one to practice implementing a segment tree.\n \nEach internal node, depending on if it i
Perhaps overkill for this problem, but this is a great opportunity for one to practice implementing a segment tree.\n \nEach internal node, depending on if it is a left (indicating it is an even index) or right child (indicating it is an odd index) of its own parent, will take on either the max or min value of it\'s two child nodes.\n \nSince `n = 2^L`, we have a total of `1 + 2 + ... + 2^L = 2^{L+1} - 1 = O(2^{L+1}) = O(2*2^L) = O(2n) = O(n)` nodes in our tree, so space and time-complexity are linear.\n\n**CODE**\n```\nclass Solution:\n    def minMaxGame(self, nums: List[int]) -> int:\n        n = len(nums)\n        \n        tree = [0] * (4 * n)\n        \n        def build(idx: int, left: int, right: int):\n            if left == right:\n                tree[idx] = nums[left]\n                return\n            mid = (left + right) // 2\n            left_idx = 2 * idx + 1\n            right_idx = left_idx + 1\n            build(left_idx, left, mid)\n            build(right_idx, mid + 1, right)\n            # root or left child\n            if idx == 0 or idx % 2 == 1:\n                tree[idx] = min(tree[left_idx], tree[right_idx])\n            # right child\n            else:\n                tree[idx] = max(tree[left_idx], tree[right_idx])\n        \n        build(0, 0, n - 1)\n        return tree[0]\n```
[]