Sorting + Binary Search + Prefix Sum | Clean Code | Standard Binary Search Approach | Java Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition for this approach is to maximize the subarray length. And if we are able 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition for this approach is to maximize the subarray length. And if we are able to achieve a subarray length of some length, say len, then that means it is possible for us to achieve a length of [0, len - 1]. And hence we are able to narrow down our search space in this way. Hence leading our way towards binary search.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- The result could be in the range of [1, n].\n- Hence we apply binary search to find the minimal length.\n- We use check function which takes length of subarray(len) as parameter and checks if it is possible to make all the elements of the subarray equal to the median(mid element) of the subarray and take the minimum value of all the subarrays, inorder for us to see if it is possible to make atleast one subarray. And then compare this value with the value of max operations. And this is how this problem can be solved.\n\n\n# Complexity\n- Time complexity: O(nlogn) -> Sorting + O(logn -> binary search * n -> check function)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(logn) -> Sorting in java internal space + O(n) -> prefix sum\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    long pref[];\n    \n    private boolean check(int[] nums, int len, long k)\n    {\n        long sum = Long.MAX_VALUE;\n        for(int j=len;j<nums.length + 1;j++)\n        {\n            int i = j - len, mid = (i + j) / 2, tar = nums[mid];\n            sum = Math.min(sum, tar * (mid - i) - (pref[mid] - pref[i]) + (pref[j] - pref[mid]) - tar * (j - mid));\n        }\n        return sum <= k;\n    }\n    \n    public int maxFrequencyScore(int[] nums, long k) {\n        Arrays.sort(nums);\n        int n = nums.length, l = 1, h = n, res = -1;\n        pref = new long[n + 1];\n        for(int i=0;i<n;i++) pref[i + 1] = pref[i] + nums[i];\n        while(l <= h)\n        {\n            int mid = l + (h - l) / 2;\n            if(check(nums, mid, k))\n            {\n                res = mid;\n                l = mid + 1;\n            }\n            else\n                h = mid - 1;\n        }\n        return res;\n    }\n}\n```\n\nPlease do let me know in the comments if it can be optimized any further. Do ask in case of any queries.\n\n![image](https://media.tenor.com/khiVwTmvkAwAAAAM/hi-brahmi-gifs.gif)\nPlz, do upvote...
['Java']