Python very clean code | Binary Search + Prefix Sum | with explainations
Intuition\n Describe your first thoughts on how to solve this problem. \nApply BS on answer (1, len(nums))\nTo check whether we can make a subarray of length l 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nApply BS on answer (1, len(nums))\nTo check whether we can make a subarray of length l same -\nIterate over all subarrays of length l and see if we can make all elems of curr subarray equal to its media within the value of k.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def maxFrequencyScore(self, nums: List[int], k: int) -> int:\n        nums.sort()\n        prefix = []\n        curr = 0\n        for n in nums:\n            curr+=n\n            prefix.append(curr)\n\n        def getMedianAndMedianIdx(x, start):\n            end = start+x-1\n            mi = (end-start)/2\n            return ((nums[(x//2)+start]+nums[((x//2)-1)+start])/2, mi+start)  if x%2==0 else (nums[(x//2)+start], int(mi)+start)\n\n        def canMakeXSame(x):\n            for j in range(x-1, len(nums)):\n                start = j - x + 1 \n                med, medIdx = getMedianAndMedianIdx(x, start)\n                if x%2:\n                    leftHalfSum = prefix[medIdx-1] if start==0 else prefix[medIdx-1] - prefix[start-1]\n                    leftHalfCount = medIdx - start\n                    rightHalfSum = prefix[j]-prefix[medIdx]\n                    rightHalfCount = j - medIdx\n                else:\n                    leftHalfSum = prefix[int(medIdx)] if start ==0 else prefix[int(medIdx)] - prefix[start-1]\n                    leftHalfCount = int(medIdx) - start + 1\n                    rightHalfSum = prefix[j] - prefix[int(medIdx)]\n                    rightHalfCount = j - int(medIdx)\n\n                if (leftHalfCount * med - leftHalfSum) + (rightHalfSum - rightHalfCount * med) <=k:\n                    return True\n            return False\n        \n        low = 1\n        high = len(nums)\n        ans = 0\n        while low<=high:\n            mid = (low+high)//2\n            if canMakeXSame(mid):\n                ans = mid\n                low = mid + 1\n            else:\n                high = mid - 1\n        return ans\n\n    \n                \n            \n        \n        \n        \n        \n```
['Python3']