Sorting | Binary Search | Sliding Window | Prefix Sum
Intuition\nSimple Sliding Window + Binary Search\n\nApply the Binary Search on Answer technique. \n\nMinimum possible freq: 1 and maxPossible Freq: nums.length\
# Intuition\nSimple Sliding Window + Binary Search\n\nApply the Binary Search on Answer technique. \n\nMinimum possible freq: 1 and maxPossible Freq: nums.length\n\nleftFreq = 1, rightFreq = nums.length;\n\nApply binary search on this range and check the feasibility of frequency equal to  midFreq where midFreq is leftFreq + (rightFreq - leftFreq) / 2;\n    \n```\n    if(possible(midFreq)) {\n        // try to increase the frequency by moving leftFreq to midFreq + 1\n    } else {\n        rightFreq = midFreq - 1;\n    }\n```\n\n    \nIn order to check the feasibility, apply the fixed size sliding window of length `midFreq` to check whether numbers in that window can be converted to the median \nof that fixed range or not while maxOperations allowed are k? \n\nIn order to do this efficiently we can apply the concept of prefix sum to quickly calculate the number of operations required to convert every number to the median element.\n    \n    NOTE: Don\'t forget to sort the array\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$(n logn)$$\n\n\n\n# Code\n```\n\n\nclass Solution {\n    \n    private boolean isPossible(int length, int[] nums, long k, long[] prefixSum) {\n        \n        int leftIdx = 0, rightIdx = 0;\n        while(rightIdx < nums.length) {\n            if(rightIdx - leftIdx + 1 < length) {\n                rightIdx++;\n                continue;\n            }\n            \n            int medianIdx = leftIdx + ((rightIdx - leftIdx) / 2);\n            long curOperations = (prefixSum[rightIdx + 1] - prefixSum[medianIdx + 1]);\n            if(medianIdx > leftIdx) {\n                curOperations -= prefixSum[medianIdx] - prefixSum[leftIdx];\n            }\n            \n            if((rightIdx - leftIdx + 1) % 2 == 0) {\n                curOperations -= nums[medianIdx];\n            }\n            \n            if(curOperations <= k) {\n                return true;\n            }\n            \n            \n            leftIdx++;\n            rightIdx++;\n        }\n        \n        return false;\n    }\n    \n    public int maxFrequencyScore(int[] nums, long k) {        \n        \n        if(nums.length == 1) {\n            return 1;\n        }\n        \n        Arrays.sort(nums);\n        \n        long[] prefixSum = new long[nums.length + 1];\n        for(int idx = 0; idx < nums.length; idx++) {\n            prefixSum[idx + 1] = prefixSum[idx] + nums[idx];\n        }\n        \n        int leftFreq = 2, rightFreq = nums.length;\n        while(leftFreq <= rightFreq) {\n            int midFreq = leftFreq + ((rightFreq - leftFreq) >> 1);\n            \n            if(isPossible(midFreq, nums, k, prefixSum)) {\n                leftFreq = midFreq + 1;\n            } else {\n                rightFreq = midFreq - 1;\n            }\n        }\n        \n        return rightFreq;\n        \n    }\n}\n```
['Java']