Clean Intuitive Binary Search
Intuition\nBinary Search on the answer/length.\n\n# Approach\nFor a sorted array, try to convert subarray of each length to all same. The element to which the w
# Intuition\nBinary Search on the answer/length.\n\n# Approach\nFor a sorted array, try to convert subarray of each length to all same. The element to which the whole subarray converges will be median of the subarray.\nFind the right subarray with sliding window technique.\n\n# Complexity\n- Time complexity:\n$$O(nlog(n))$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\ntypedef vector<int> VI;\ntypedef long long ll;\ntypedef vector<ll> VL;\n\nclass Solution {\npublic:\n    bool poss(int len, VI &nums, VL &prefix, ll k){\n        int n = nums.size();\n        for(int start=0;start <= n-len;start++){\n            int end = start+len-1;\n            //first find the median index\n            int median = start + (end - start)/2;\n            int c1 = median-start, c2 = end-median;\n            ll sum1 = (median>0 ? prefix[median-1] : 0) - (start>0 ? prefix[start-1] : 0);\n            ll sum2 = prefix[end] - prefix[median];\n            ll change1 = c1 *1LL* nums[median] - sum1;\n            ll change2 = sum2 - c2 *1LL* nums[median];\n            if(change1 + change2 <= k){\n                return true;\n            }\n        }\n        return false;\n    }\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        //bineary search over the count\n        sort(nums.begin(), nums.end());\n        int n = nums.size();\n        int lo = 1, hi = n;\n        VL prefix(n);\n        for(int i=0;i<n;i++){\n            prefix[i] = nums[i] + (i>0 ? prefix[i-1] : 0);\n        }\n        while(lo < hi){\n            //TTTTFFFF\n            //last true\n            int mid = lo + (hi - lo + 1)/2;\n            if(poss(mid, nums, prefix, k)){\n                lo = mid;\n            }\n            else{\n                hi = mid-1;\n            }\n        }\n        return lo;\n    }\n};\n```
['C++']