Python 32% | score range parsing, but not prefix-sum
Intuition\r\nRather than using prefix-sum, I began with the awareness that this problem can be broken into two subproblems:\r\n1. for each number in array, what
# Intuition\r\nRather than using prefix-sum, I began with the awareness that this problem can be broken into two subproblems:\r\n1. for each number in array, what\'s the range of k? so that in the end this number can score?\r\n2. given certain intervals, find out the very first index that has the most intervals covering it.\r\n\r\nIt\'s not very fast compare to prefix-sum solution, but it got a steady 32% time consume outcome\r\n# Approach\r\n1. parse through nums, get score range of k for each number\r\n2. building two smallest heaps of range start-index and end-indes\r\n3. imaging using a vertical line scanning through number axis from 0 to L-1, every time you meet a start-index, you get 1 point, loss 1 if you meet end-index, keep updating max_points and corresponding k\r\n4. voila~ \r\n\r\n# Code\r\n```\r\nfrom heapq import heappop, heappush\r\n\r\nclass Solution:\r\n    def bestRotation(self, nums):\r\n        L = len(nums)\r\n\r\n        score_ranges = []  # range of k that will get a score\r\n        for idx, val in enumerate(nums):  # score_idx in [val, L-1]\r\n            if idx >= val: score_ranges.append((0, idx - val))  # idx left\r\n            if idx < L - 1: score_ranges.append((idx + 1, min(L - 1, (L - val) + idx)))  # idx right\r\n\r\n        starts, ends = [], [] # notice these are possible k\'s\r\n        for start, end in score_ranges:\r\n            heappush(starts, start)\r\n            heappush(ends, end)\r\n\r\n        max_k, max_points, point = 0, 0, 0\r\n        while starts:  # chance to get higher score\r\n            if starts[0] <= ends[0]: # score before loss points\r\n                point += 1\r\n                if point > max_points:\r\n                    max_k, max_points = starts[0], point\r\n                heappop(starts)\r\n            else:\r\n                point -= 1\r\n                heappop(ends)\r\n\r\n        return max_k\r\n```
['Array', 'Sorting', 'Heap (Priority Queue)', 'Python', 'Python3']