[Python] Sort + sliding window type approach
Intuition\n Describe your first thoughts on how to solve this problem. \nThis problems calls for sorting and a sliding window type approach. \nWe test each inde
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problems calls for sorting and a sliding window type approach. \nWe test each index i, at each index we try to increment the window as much as we can, by chosing greedily to go left or right.\n\nleft = represents the index of the last element inclusive we can achieve to the left\nright = represents the index of the last element inclusive we can achieve to the right\n\nNaive algorithm O(n^2)\n```\nFirst Sort the array (n log n)\nFor each index i:\n    while budget >= 0:\n        check if closest element is the next left or the next right one\n        pick the closest element if budget available\n        increment right or left\n    res = max(res, right - left + 1) \n```\nThis is a good approach, but not fast enough\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThey key here is noticing that as we advance in indices, the window of legal values will advance to the right.\n\nAs we center our potential result on a new bigger value, the smaller numbers in the array become less accessible and the bigger ones more accessible => sliding to the right.\n\nThe goal is to use the previous legal window to get the new one.\nFor that we need to compute the new budget as we move to the next element in the sorted list.\n\nThis is easy if we keep track of the sum_before, and sum_after.\nSum_before += nb_element_left * (nums[i] - nums[i-1])\nSum_after -= nb_element_right * (nums[i] - nums[i-1])\n\nThen we can update the previous sliding windown in the same style as with the naive algorithm, the only subtility is that we need to unchoose from left as long as the next right number is more interesting.\n\n# Complexity\n### Time complexity:\nO(nlog n) for sorting\nThen each value is at most included once in the sliding window, and removed once, so the iteration is O(n)\n\n### Space complexity \nO(n) since we store the number array\n\n# Code\n```\nfrom typing import List\nclass Solution:\n    def maxFrequencyScore(self, nums: List[int], k: int) -> int:\n        nums.sort()\n        res = 0\n        n = len(nums)\n\n        sum_before = 0 #stores the current cost to the left of our value\n        sum_after = 0 #stores the current cost to the right of our value\n        left = 0 #represents the max index we can go to the left\n        right = 0 #represents the max index we can go to the right\n\n        for i in range(n):            \n            \n            #this is the tricky part, updating the sums given we are at a new element\n            if i > 0:\n                # we need to increase sum_before by the new numbers to our left times the delta\n                sum_before += (i - left) * (nums[i] - nums[i-1])\n\n                # for sum_right it\'s a bit tricky, either we were able to achieve right before\n                # so the new sum right gets decrease by the delta times the number of elements to the right\n                if i < right:\n                    sum_after -= (right + 1 - i) * (nums[i] - nums[i-1])\n                # or we could not achieve right before, so the sum_right gets back to 0\n                else:\n                    right = max(right,i)\n                    sum_after = 0\n            \n            #first unchose from left as long as right offers a better choice\n            while left < i and (right < n-1 and nums[i] - nums[left] > nums[right+1] - nums[i]) or (sum_before > k):\n                sum_before -= nums[i] - nums[left]\n                left += 1\n            \n\n            #then choose, apply classic logic, if better right chose right, else chose left, if possible\n            while k >= sum_after + sum_before:\n                \n                #first we decide if we want to go left or right, or neither if at both extremities\n                best_right = None\n                if left == 0 and right == n-1:\n                    best_right == None\n                elif left == 0 or (right < n-1 and nums[i] -  nums[left-1] > nums[right+1] - nums[i]):\n                    best_right = True\n                else: \n                    best_right = False\n                \n\n                #then we check that we can indeed go in that direction\n                if best_right == None:\n                    break\n                if best_right:\n                    if k - (sum_after + sum_before) >= nums[right+1] - nums[i]:\n                        sum_after += nums[right+1] - nums[i]\n                        right += 1\n                    else:\n                        break\n                else:\n                    if k - (sum_after + sum_before) >= nums[i] - nums[left-1]:\n                        sum_before += nums[i] - nums[left-1]\n                        left -= 1\n                    else:\n                        break\n            res = max(res, right - left + 1)\n        \n        return res\n```
['Python3']