intuition of sliding window soln
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nstep 1) as the order in
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nstep 1) as the order in which you choose the elements doesnt matter hence we can first sort our vector. \n\nstep 2) now in this vector , we will check which subarrays can be converted (in k operations) to a single element(i.e median of that subarray ; always remember if you have to converge all the elements of an array to single element in least operations than that converging element is always the median of that array). \n\nnow why we are sorting the array ? and why we are only considering only subarrays ?  \n\nans-> just take a seq [1 , 2, 3, 5, 7]. here the medium of array is 3. so we want to convert every element to 3. now just think , first you would try to spend 4 operations to convert 7 to 3 , or spend 2 operations to convert 5 to 3. obviously we would first try to convert the elements which are nearer to median and then see if we have operations left to converge the farther elements to median.\n\nsteps 3) simply apply sliding window. size of subarray will tell the number of elements which have been converted into single element (hence the freq of that element).if num of operations exceed k then it means you cant convert those subarray elements into one hence increment the starting window pointer and continue.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\nprivate:\n    long long numOfOpsCalculator(int i, int j, vector<int>& nums, vector<long long> &prefixSum, int n) {\n        \n        int medianIndex = (i+j)/2;\n        int median = nums[medianIndex];\n        long long ops = 0;\n            \n        long long leftSum = i > 0 ? prefixSum[medianIndex] - prefixSum[i - 1] : prefixSum[medianIndex];\n        \n        long long rightSum = medianIndex > 0 ? prefixSum[j] - prefixSum[medianIndex - 1] : prefixSum[j];\n        \n        ops += (medianIndex - i + 1)*(long long)nums[medianIndex] - leftSum;\n        ops += rightSum - (j - medianIndex + 1)*(long long)nums[medianIndex];\n        return ops;\n    }\npublic:\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        int n = nums.size();\n        \n        sort(nums.begin(), nums.end());\n        int i = 0, j = 0, maxFreq = 0;\n        vector<long long> prefixSum(n, 0);\n        \n        while(j < n) {\n            prefixSum[j] = j > 0 ? prefixSum[j-1] + nums[j] : nums[j];\n            \n            long long numOfOps = numOfOpsCalculator(i, j, nums, prefixSum, n);\n            \n            while(numOfOps > k) {\n                i++;\n                numOfOps = numOfOpsCalculator(i, j, nums, prefixSum, n);\n            }\n            \n            maxFreq = max(maxFreq, j-i+1);\n            \n            j++;\n        }\n        \n        return maxFreq;\n    }\n};\n```
['Two Pointers', 'Sliding Window', 'C++']