O(N) Forward/Backward Scan in Python3, Beating 100%
Approach\nThis problem is about to find a pivot $p$ to split nums into two parts with the maximum value of $(l_2 - l_1 + 1) + (r_2 - r_1 + 1)$ for $l_1 \leq l_2
# Approach\nThis problem is about to find a pivot $p$ to split `nums` into two parts with the maximum value of $(l_2 - l_1 + 1) + (r_2 - r_1 + 1)$ for $l_1 \\leq l_2 \\leq p \\leq r_1 \\leq r_2$ and $\\mathrm{nums}[l_2] - \\mathrm{nums}[l_1] \\leq k, \\mathrm{nums}[r_2] - \\mathrm{nums}[r_1] \\leq k$. \nTo speed up, we can precompute the best $(l_1, l_2)$ for each $p$, and loop for the best $(r_1, r_2)$ in the backward direction and find the best value of $(l_2 - l_1 + 1) + (r_2 - r_1 + 1)$. \nFor the two linear scan, the overall complexity is only $O(N)$.\n\n# Complexity\n- Time complexity: $O(N)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(N)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def maximizeWin(self, prizes: List[int], k: int) -> int:\n        if prizes[-1] - prizes[0] <= k:\n            return len(prizes)\n        forward = [0, 1]\n        offset = 0\n        for i in range(1, len(prizes)):\n            while prizes[i] - prizes[offset] > k:\n                offset += 1\n            forward.append(i - offset + 1)\n        offset = len(prizes) - 1\n        backward = 1\n        ans = backward + forward[-1]\n        for i in range(offset - 1, -1, -1):\n            while prizes[offset] - prizes[i] > k:\n                offset -= 1\n            backward = max(backward, offset - i + 1)\n            ans = max(ans, backward + forward[i])\n        return ans```
['Two Pointers', 'Sliding Window', 'Python3']