C++ - Easy to understand - Sliding window + Prefix sum O(n)
Intuition\n Describe your first thoughts on how to solve this problem. \nSorting: Min cost when we try to make those elements that have less distance equal. Tho
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSorting: Min cost when we try to make those elements that have less distance equal. Those elements can be obtained when we sort the array.\n\nSliding window: Imagine like this, you sit at index i and you do not know should you increase and decrease how many elements before and after index i to equal to nums[i] to get the max freq right? But you know for sure if you can make a window from [i, j] to equal a number (any number in the window [i, j]), then you can make any window that has len less than j - i + 1 and inside the [i, j] => This is the signal of sliding window (you can for sure making smaller window valid if the outer window is already valid).\n\nBut then what is the element you should choose inside the window? If you know the fact that it\'s the median of window that always take min cost then it\'s really easy. For each window you traverse just try to increase/decrease all the elements to window\'s median and check the cost for that operations is valid or not.\n    => If yes increase window size. If no schrink the window size.\n\nFor median fact, you should try these problems to have a deep understand (do by order, each sub-problem will give you another aspect of this huge problem):\nhttps://cses.fi/problemset/task/1076\nhttps://cses.fi/problemset/task/1074\nhttps://cses.fi/problemset/task/1077\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    long long getCost(int l, int r, vector<long long> &prf, vector<int> &nums) {\n        int m = l + (r - l)/2;\n        int median = nums[m];\n        long long leftCost = 1LL*(m - l + 1)*median - (prf[m] - prf[l] + nums[l]);\n        long long rightCost = 1LL*(prf[r] - prf[m] + nums[m]) - 1LL*(r - m + 1)*median;\n        return leftCost + rightCost;\n    }\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        sort(nums.begin(), nums.end());\n        vector<long long> prf(nums.size());\n        for (int i = 0; i < nums.size(); i++) {\n            prf[i] = i == 0 ? 1LL*nums[i] : 1LL*nums[i] + prf[i - 1];\n        }\n        int mx = INT_MIN;\n        int l = 0, r = 0;\n        while (r < nums.size()) {\n            long long cost = getCost(l, r, prf, nums);\n            \n            // invalid window\n            while (cost > k) {\n                l++;\n                cost = getCost(l, r, prf, nums);\n            }\n\n            // valid window\n            mx = max(mx, r - l + 1);\n\n            r++;\n        }\n        return mx;\n    }\n};\n```
['C++']