CPP | Sorting | Prefix Sum | Window Sliding | Median
Time Complexity : O(nlogn)\nSpace Complexity: O(n)\n\n\nclass Solution {\npublic:\n    typedef long long ll;\n    int maxFrequencyScore(vector<int>& v, long lon
**Time Complexity** : `O(nlogn)`\n**Space Complexity**: `O(n)`\n\n```\nclass Solution {\npublic:\n    typedef long long ll;\n    int maxFrequencyScore(vector<int>& v, long long k) {\n        ll start = 0, end = 0, n = v.size(), ans = 0;\n        sort(v.begin(), v.end());\n        vector<ll> ps(1);\n        for(int x : v) {\n            ps.push_back(ps.back() + x);\n        }\n        while(end < n) {\n            end += 1;\n            ll midx = start + (end - start) / 2;\n            ll med = v[midx]; // median of current subarray i.e from start -> end\n            ll leftLen = midx - start; // length of left sub array\n            ll rightLen = end - midx; // length of right sub array\n            ll leftSum = leftLen * med - ps[midx] + ps[start]; // sum that is required to change left sub array elements equal to med\n            ll rightSum = ps[end] - ps[midx] - rightLen * med; // sum that is required to change right sub array elements equal to med\n            ll s = leftSum + rightSum; // // total sum that is required to change current sub array elements equal to med\n            while(s > k) {\n                start += 1;\n                midx = start + (end - start) / 2;\n                med = v[midx];\n                leftLen = midx - start;\n                rightLen = end - midx;\n                leftSum = leftLen * med - ps[midx] + ps[start];\n                rightSum = ps[end] - ps[midx] - rightLen * med;\n                s =  leftSum + rightSum;\n            }\n            ans = max(ans , end - start);\n        }\n        return ans;\n    }\n};\n```
['Sliding Window', 'Sorting', 'Prefix Sum', 'C++']