[Python] heap with moving target O(NlogN)
The official solution of interval stabbing at O(N) is definitely ingenious. Here is another idea with heap/pirority queue at O(NlogN) for reference.\n\nObservat
The official solution of interval stabbing at O(N) is definitely ingenious. Here is another idea with heap/pirority queue at O(NlogN) for reference.\n\nObservations:\n\nLet\'s directly check the difference between index and corresponding value, with one example\n\nIndex: 0, 1, 2, 3, 4, 5\nvalues: 1, 3, 0, 2, 4, 5\ndiff: -1, -2, 2, 1, 0, 0\n\nAnd the score is just the number of diffs >= 0, which is 4 at zero rotation.\n\nWhen we rotate once:\n- The first diff will be increased by 5 since value 1 will be moved to index 5, diff becomes 5 - 1 == (0 - 1) + 5\n- All other diffs are actually decreased by 1, because their corresponding indices are reduced by 1.\n\nSo the diff after one rotation is: -3, 1, 0, -1, -1, 4, now the number of non-negative diff is 3.\n\nNote that if we keep doing in this way, it is just brute force with O(N^2) time complexity. So we need something better:\n\n1) Instead of updating all other indices, why not we just update the target which we compare diff against. So after one rotation, the target becomes 1 from 0, the first diff increases by 6 while moving to the last position, and all other diffs stay the same, like this: -2, 2, 1, 0, 0, 5. And we just need to find out the number of diffs >= target (1), which is still 3.\n\n2) Instead of moving the diff positions along the way, we can just simply maintain a pointer for the position where the diff needs to be increased by N (=6 in this example) along the rotation: 5, -2, 2, 1, 0, 0. It doesn\'t change the score.\n\nCombining 1) and 2), here is how the rotation looks now. note the highlighted diff which get increased by N at correspoinding rotation.\n\n![image](https://assets.leetcode.com/users/images/206ee963-a8ff-40bb-b3f6-a5f4690cc996_1644507790.0746312.png)\n\nWe can use a heap to keep track of all diffs larger than target. At each rotation, pop out diffs which are smaller than current target, then increase the one diff needed, push it into the heap. The score is just the size of the heap, as shown above.\n\nCode:\n\n```\nclass Solution:\n    def bestRotation(self, nums: List[int]) -> int:\n        diff = [i - nums[i] for i in range(len(nums))]\n        \n        target = 0\n        qualified = []\n        for d in diff:\n            if d >= target:\n                heappush(qualified, d)\n        smallest_rotate = 0\n        highest_score = len(qualified)\n        \n        \n        for rotate in range(1, len(nums)):\n            target += 1\n            while qualified and qualified[0] < target:\n                heappop(qualified)\n            modified = diff[rotate-1] + len(diff)\n            heappush(qualified, modified)\n            score = len(qualified)\n            if score > highest_score:\n                smallest_rotate = rotate\n                highest_score = score\n        \n        return smallest_rotate\n\n```\n\n\n\n\n\n\n
['Heap (Priority Queue)', 'Python']