Median + Binary Search |  C++ | Simple Clean code
Intuition\nCan solve through binary search on the subarray size and then making all the elements of the subarray equal to the subarray\'s median and if the tota
# Intuition\nCan solve through binary search on the subarray size and then making all the elements of the subarray equal to the subarray\'s median and if the total operation required to make the subarray equal to its median then the answer is definitely going to be greater than the current subarray\'s size.\n\n# Approach\n1. Sort the array and the answer will always be a subarray of this sorted array, coz the individual distances of the elements from the common element will be less when the elements are close to themselves, hence sorting the array.\n2. Apply binary search on the answer i.e the subarray size.\n3. Now for each subarray of size mid, you need to check if the numbers of operations required to convert all the elements of this subarray to some common element(which btw would be the median on this subarray, by definition) <= K, then this size i.e mid is a valid subarray size, and we should now look for more bigger subarrays.\n4. for checking that given the size of a subarray whether or not it\'s a doable size or not, there\'s a formula mentioned in the isSubarrayExistsForSize, which you\'ll be able to find after doing some math, basically the answer for the current window is related to the previous window of the same size.\n\n# Complexity\n- Time complexity:\nO(NLogN)\n\n- Space complexity:\nO(1)\n\n# Code\n```\nclass Solution {\npublic:\n\n    bool isSubarrayExistsForSize(vector<int>&ar, long long k, int subSize){\n\n        // step 1 -> Find the ans for the first window of length subSize.\n\n        // step 2 -> Have a loop to find the answers for rest of the windows.\n        int n = ar.size();\n\n        long long opeationsPrev = 0;\n        long long operationsCurr = 0;\n        int prev_median = ar[subSize/2];\n\n        for(int i=0;i<subSize;i++){\n            opeationsPrev += 1LL*abs(ar[i] - prev_median);\n        }\n\n        if(opeationsPrev <= k){\n            return true;\n        }\n\n        for(int i = 1;i <= n - subSize; i++){\n            int curr_median_index = i+(subSize/2);\n            int curr_median = ar[curr_median_index];\n            int si1 = curr_median_index - i;\n            int si2 = subSize - si1 - 1;\n\n            operationsCurr = opeationsPrev + 1LL*ar[i-1] + 1LL*ar[i-1+subSize] - 1LL*prev_median - 1LL*curr_median + 1LL*((curr_median - prev_median)*(si1-si2));\n\n            if(operationsCurr <= k){\n                return true;\n            }\n\n            prev_median = curr_median;\n            opeationsPrev = operationsCurr;\n        }       \n\n        return false;\n    }\n\n    int maxFrequencyScore(vector<int>& ar, long long k) {\n        int n = ar.size();\n        sort(ar.begin(), ar.end());\n\n        int ms = -1;\n        int s = 1, e = n;\n        while(s <= e){\n            int mid = (s + e)/2;\n\n            // mid is the freq of the elements.\n            // Also its the size of the subarray which eventually will have all equal elements.\n\n            if(isSubarrayExistsForSize(ar, k, mid)){\n                ms = mid;\n                s = mid + 1;\n            }\n            else{\n                e = mid - 1;\n            }\n        }\n\n        if(ms == -1){\n            return -1;\n        }\n\n        return ms;\n    }\n};\n```
['C++']