✅Beats 100% - Explained - Prefix Sum + Binary Search - C++/Java/Python/JS
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to maximize the score, which is the frequency of the most frequent el
![Screenshot 2023-12-17 131902.png](https://assets.leetcode.com/users/images/04d37aea-e7f5-4f74-806f-29e3f30f8a92_1702799505.7847507.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to maximize the score, which is the frequency of the most frequent element in the array. The operations allowed are incrementing or decrementing the values at any index in the array. The approach involves using binary search to find the optimal value for the most frequent element and then adjusting the array accordingly.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sort the array to make it easier to perform binary search.\n2. Use binary search to find the target value for the most frequent element.\n3. For each candidate target value, calculate the cost of making the array elements equal to the target value.\n4. Adjust the array elements to minimize the cost while staying within the allowed number of operations (k).\n5. Update the maximum score based on the frequency of the most frequent element achieved.\n6. Continue the binary search until the optimal target value is found.\n\n# Complexity\n- Sorting the array takes O(n log n) time.\n- Binary search is performed in each iteration, taking O(log n) time.\n- The inner while loop adjusts the array elements and takes O(n) time in the worst case.\n- Overall, the time complexity is O(n log n * log(max(nums))).\n- The space complexity is O(n) for the prefix sum array.\n- The algorithm uses binary search to optimize the target value, and then linearly adjusts the array to find the maximum score.\n\n# Code\n```java []\nclass Solution {\n    public int maxFrequencyScore(int[] nums, long k) {\n        Arrays.sort(nums);\n        int n = nums.length;\n        long[] prefixSum = new long[n + 1];\n        for (int i = 0; i < n; i++) {\n            prefixSum[i + 1] = prefixSum[i] + nums[i];\n        }\n        int start = 0;\n        int end = 1;\n        int out = 1;\n        while (end < n) {\n            end++;\n            int mid = (start + end) / 2;\n            long target = nums[mid];\n            long cost = (target * (mid - start) - (prefixSum[mid] - prefixSum[start])) + (prefixSum[end] - prefixSum[mid] - target * (end - mid));\n            while (start < end && cost > k) {\n                start++;\n                mid = (start + end) / 2;\n                target = nums[mid];\n                cost = (target * (mid - start) - (prefixSum[mid] - prefixSum[start])) + (prefixSum[end] - prefixSum[mid] - target * (end - mid));\n            }\n            out = Math.max(out, end - start);\n        }\n        return out;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        sort(nums.begin(), nums.end());\n\n    int n = nums.size();\n    vector<long long> prefixSum(n + 1, 0);\n\n    for (int i = 0; i < n; ++i) {\n        prefixSum[i + 1] = prefixSum[i] + nums[i];\n    }\n\n    int start = 0;\n    int end = 1;\n    int maxScore = 1;\n\n    while (end < n) {\n        ++end;\n        int mid = (start + end) / 2;\n        long long target = nums[mid];\n        long long cost = (target * (mid - start) - (prefixSum[mid] - prefixSum[start])) + (prefixSum[end] - prefixSum[mid] - target * (end - mid));\n\n        while (start < end && cost > k) {\n            ++start;\n            mid = (start + end) / 2;\n            target = nums[mid];\n            cost = (target * (mid - start) - (prefixSum[mid] - prefixSum[start])) + (prefixSum[end] - prefixSum[mid] - target * (end - mid));\n        }\n\n        maxScore = max(maxScore, end - start);\n    }\n\n    return maxScore;\n    }\n};\n```\n```Python []\nclass Solution(object):\n    def maxFrequencyScore(self, nums, k):\n        nums.sort()\n\n        n = len(nums)\n        prefix_sum = [0] * (n + 1)\n\n        for i in range(n):\n            prefix_sum[i + 1] = prefix_sum[i] + nums[i]\n\n        start = 0\n        end = 1\n        max_score = 1\n\n        while end < n:\n            end += 1\n            mid = (start + end) // 2\n            target = nums[mid]\n        \n            cost = (target * (mid - start) - (prefix_sum[mid] - prefix_sum[start])) + (prefix_sum[end] - prefix_sum[mid] - target * (end - mid))\n        \n            while start < end and cost > k:\n                start += 1\n                mid = (start + end) // 2\n                target = nums[mid]\n                cost = (target * (mid - start) - (prefix_sum[mid] - prefix_sum[start])) +(prefix_sum[end] - prefix_sum[mid] - target * (end - mid))\n\n            max_score = max(max_score, end - start)\n\n        return max_score\n        \n```\n```JavaScript []\n/**\n * @param {number[]} nums\n * @param {number} k\n * @return {number}\n */\nvar maxFrequencyScore = function(nums, k) {\n    nums.sort((a, b) => a - b);\n\n    const n = nums.length;\n    const prefixSum = new Array(n + 1).fill(0);\n\n    for (let i = 0; i < n; ++i) {\n        prefixSum[i + 1] = prefixSum[i] + nums[i];\n    }\n\n    let start = 0;\n    let end = 1;\n    let maxScore = 1;\n\n    while (end < n) {\n        ++end;\n        const mid = Math.floor((start + end) / 2);\n        const target = nums[mid];\n        let cost = (target * (mid - start) - (prefixSum[mid] - prefixSum[start])) + (prefixSum[end] - prefixSum[mid] - target * (end - mid));\n\n        while (start < end && cost > k) {\n            ++start;\n            const mid = Math.floor((start + end) / 2);\n            const target = nums[mid];\n            cost = (target * (mid - start) - (prefixSum[mid] - prefixSum[start])) + (prefixSum[end] - prefixSum[mid] - target * (end - mid));\n        }\n\n        maxScore = Math.max(maxScore, end - start);\n    }\n\n    return maxScore;\n};\n```\n![upvote.png](https://assets.leetcode.com/users/images/0c1d94fa-c5ae-49a4-a4d4-936c82e79823_1702799650.7513952.png)\n
['Binary Search', 'Prefix Sum', 'Python', 'C++', 'Java', 'JavaScript']