Beats 100% | Thought Process | Prefix Sum | Python
Binary Search + Prefix Sum\nMy first solution is to find out each possible window for each arary number using merging sorted array, because the final value with
### Binary Search + Prefix Sum\nMy first solution is to find out each possible window for each arary number using merging sorted array, because the final value with the most frequency must appear in the array. We can try to change all values to each one possible value `nums[i]`.\n```\n1. create a counter on the array, and sort the key\n2. for each key, we expand the window centering at the key using merging sorted array\n3. move the pointer if the distance from the center is smaller than the other side. \n4. return the maximum window + the frequency of the center\n```\nHowever, this solution exceeds the time limits.\nObviously, the expanding window solution is too slow.\nSo finding the length of window seems promising. How can we find out the longest window?\nbinary search on the window length. then we can change the problem to be given the length of window, can we change all values within the window to the same value with `k` operation. \n\n**But which number should we change all values within the window to?**\nThen we can convert the problem to be what\'s the unique number we should change all values to with the minimum operatoins.\n**greedy**\nThe gready approach is to change all values to the `median` value. If the length of windwo is odd, it is obvious that the `median` is `nums[mid]`, but what if the length is even? the `median` is the average of the two mid values.\nactually, the operation is the same either side we choose. You can try this out given example of `[2,4,6,8]` by changing all to `4` and `6`.\nSo the median can be unified to `nums[mid]`.\n\n**How can we know whether we can change all values to the median?**\nWith the above observation, we can increase all values that smaller than `median` and decrease all values that are larger than `median`. But how many operations we need?\nBasically, given range `[i:j]`, we need `median * (mid - i) - sum(nums[i:mid]) + sum(nums[mid:j]) - median * (j - mid)` operations. You can think about why.\nThen it induces the prefix sum.\n\nthen we can get the final algorithm\n```\n1. sort the nums.\n2. calculate the prefix sum\n3. for each length of window using binary search, try each possible window to see if we can make all values to be the median\n4. use prefix to calculate how many operations we need to do so.\n5. return the longest length\n```\n\n```python\ndef maxFrequencyScore(self, nums: List[int], k: int) -> int:\n\tnums.sort()\n    prx = [0]\n    for num in nums:\n\t\tprx.append(prx[-1] + num)\n            \n\tdef possible(length):\n\t\tfor right in range(length, len(nums) + 1):\n\t\t\tleft = right - length\n\t\t\tmid = left + (right - left) // 2\n\t\t\tmedian = nums[mid]\n\t\t\tneed = (mid - left + 1) * median -  (prx[mid + 1] - prx[left]) + (prx[right] - prx[mid + 1]) - median * (right - mid - 1)\n\t\t\tif need <= k:\n\t\t\t\treturn True\n\t\treturn False\n                    \n\tlow, high = 1, len(nums)\n\twhile low < high:\n\t\tmid = low + (high - low + 1) // 2\n\t\tif possible(mid):\n\t\t\tlow = mid\n\t\telse:\n\t\t\thigh = mid - 1\n\treturn low\n```\n\n*Time Complexity*= **O(NlgN)**\n*Space Complexity*= **O(N)**\n\n\n\n
['Binary Tree', 'Prefix Sum']