Easy Implementation || Binary Search || Sliding Window || Prefix Sum
Approach\n- Assume the answer is x.\n- Firstly we sort the array now take window of x and try to make elements in that window equal.\n- We can make each element
# Approach\n- Assume the answer is x.\n- Firstly we **sort** the array now take window of x and try to make elements in that window equal.\n- We can make each element in that window to the median because median will take the minimum operations.\n- Hence we need to maximize the value of x.\n- For that I have done the **Binary Search** on window and search for each window in the given array.\n- That can be done using some manipulation.\n- Suppose elements are {a1, a2, a3, a4, a5}\n- mid element = a3 and we try to make every element in this window to a3\n- so, left part from position 3 have total operations will be =>\n(a3 - a3) + (a3 - a2) + (a3 - a1).\n- so, right part from position 3 have total operations will be =>\n(a5 - a3) + (a4 - a3).\n- Total number of operations = left + right.\n\n# Complexity\n- Time complexity: O(nlogn)\n- Space complexity: O(n)\n\n# Code\n```\nclass Solution {\npublic:\n  long long operations(int index, int L, int R, vector<int>& nums, vector<long long>& P) {\n    return (index - L + 1) * 1LL * nums[index] - (P[index] - (L != 0 ? P[L - 1] : 0)) + (P[R] - P[index]) - (R - index) * 1LL * nums[index];\n  }\n  \n  bool possible(vector<long long>& prefix, vector<int>& nums, int length, long long k) {\n    for(int i = 0; i + length - 1 < (int) nums.size(); i++) {\n      int L = i;\n      int R = i + length - 1;\n      if(operations(L + (length / 2), L, R, nums, prefix) <= k) {\n        return true;\n      }\n      if(length % 2 == 0) {\n        if(operations(L + (length / 2) - 1, L, R, nums, prefix) <= k) {\n          return true;\n        }\n      }\n    }\n    return false;\n  }\n  \n  int maxFrequencyScore(vector<int>& nums, long long k) {\n    \n    sort(nums.begin(), nums.end());\n    \n    vector<long long> prefix((int) nums.size());\n    for(int i = 0; i < (int) nums.size(); i++) {\n      prefix[i] = nums[i];\n      if(i != 0) {\n        prefix[i] += prefix[i - 1]; \n      }\n    }\n    \n    int ans = 0;\n    int l = 1, h = (int) nums.size();\n    while(l <= h) {\n      int mid = (l + h) >> 1;\n      if(possible(prefix, nums, mid, k)) {\n        ans = mid;\n        l = mid + 1;\n      }\n      else {\n        h = mid - 1;\n      }\n    }\n    return ans;\n  }\n};\n```
['Binary Search', 'Sliding Window', 'Prefix Sum', 'C++']