Sliding Window + Prefix Sum || Beats 85% sumbissions.
Try https://leetcode.com/problems/frequency-of-the-most-frequent-element/description/ before moving Ahead.\n### Approach and Intuition:\n\n1. Sort the Array:\n 
### Try https://leetcode.com/problems/frequency-of-the-most-frequent-element/description/ before moving Ahead.\n### Approach and Intuition:\n\n1. **Sort the Array**:\n   The `nums` array is sorted first using `Arrays.sort(nums)` so that the numbers are in ascending order. This helps in applying the frequency adjustments efficiently because similar values will be grouped together.\n\n2. **Prefix Sum Array**:\n   A prefix sum array `prefix` is constructed to allow for efficient range sum queries, which help in calculating the total operations needed to make all elements within a range equal to a chosen "target" element (midpoint element in the window). This reduces the time complexity compared to recalculating sums on the fly.\n\n3. **Sliding Window with Binary Search**:\n   A sliding window approach is employed where two pointers, `start` and `end`, are used to define a window in the sorted array. Within the window, the midpoint (`mid = start + (end - start) / 2`) is chosen to be the target element to which the other elements are adjusted.\n   \n   For each window, the following is computed:\n   - The number of operations required to make all elements from `start` to `mid` equal to `nums[mid]` (`left` side).\n   - The number of operations required to make all elements from `mid+1` to `end` equal to `nums[mid]` (`right` side).\n\n4. **Operations Check**:\n   The total number of steps/operations (`steps`) is computed by combining the left and right adjustments. If the number of steps exceeds the allowed limit `k`, the window is shrunk from the left (`start++`). Otherwise, the size of the current window (`end - start + 1`) is compared to the maximum possible answer.\n\n5. **Sliding the `end` Pointer**:\n   After processing each window, the `end` pointer is incremented to explore larger subarrays.\n\n### Time Complexity:\n1. **Sorting the Array**: Sorting the `nums` array takes \\(O(n*log n)\\), where `n` is the length of the array.\n   \n2. **Prefix Sum Calculation**: Constructing the prefix sum array takes \\(O(n)\\), as it requires a single pass through the array.\n   \n3. **Sliding Window**: For each position of `end`, the binary search-based window adjustment is done. In the worst case, the binary search process takes \\(O(log n)\\), and adjusting the `start` pointer takes linear time in the worst case. Thus, the sliding window step contributes \\(O(n*log n)\\).\n\n### Overall Time Complexity:\n- Sorting: \\(O(n*log n)\\)\n- Prefix Sum: \\(O(n)\\)\n- Sliding Window: \\(O(n*log n)\\)\n\nThus, the overall time complexity is \\(O(n*log n)\\).\n\n### Space Complexity:\n- The space complexity is dominated by the prefix sum array, which takes \\(O(n)\\) space, and other auxiliary variables (pointers, etc.), which are \\(O(1)\\).\n  \nThus, the space complexity is \\(O(n)\\).\n\n### Summary:\n- **Time Complexity**: \\(O(n*log n)\\)\n- **Space Complexity**: \\(O(n)\\)\n\nThis approach efficiently handles the problem by combining sorting, prefix sums, and a sliding window technique to maximize the frequency of the target element within a bounded number of operations (`k`).\n\n# Code\n```java []\nclass Solution {\n    public int maxFrequencyScore(int[] nums, long k) {\n        Arrays.sort(nums);\n        int end =0;\n        int start=0;\n        long[] prefix = new long[nums.length];\n        prefix[0]=(long)nums[0];\n        for(int i=1;i<nums.length;i++){\n            prefix[i] = prefix[i-1]+(long)nums[i];\n        }\n        int answer = 0;\n        while(end<nums.length){\n            int mid = start + (end-start)/2;\n            long left = 0;\n            long right = 0;\n            if(mid-1>=0 && start-1>=0) left = prefix[mid-1]-prefix[start-1];\n            else if(mid-1>=0 && start-1<0) left = prefix[mid-1];\n            right = prefix[end]-prefix[mid];\n            long steps = (nums[mid]*(long)(mid-start)-left)+ (right - nums[mid]*(long)(end-mid));\n            while(steps>k){\n                start++;\n                mid = start + (end-start)/2;\n                left = 0;\n                right = 0;\n                if(mid-1>=0 && start-1>=0) left = prefix[mid-1]-prefix[start-1];\n                else if(mid-1>=0 && start-1<0) left = prefix[mid-1];\n                right = prefix[end]-prefix[mid];\n                steps = (nums[mid]*(long)(mid-start)-left)+ (right - nums[mid]*(long)(end-mid));\n            }\n            answer = Math.max(answer,end-start+1);\n            end++;\n        }\n\n         return answer;\n        \n    }\n}\n```
['Sliding Window', 'Prefix Sum', 'Java']