binary search on solution beats 100% C++
Intuition\nmaximaize between:\n1- the max frequency after [0, numOfOperation] operations belongs to a number in nums\n2- the max frequency after [0, numOfOperat
# Intuition\nmaximaize between:\n1- the max frequency after [0, numOfOperation] operations belongs to a number in nums\n2- the max frequency after [0, numOfOperations] operations belongs to a number not in nums\n\n# Approach\n1- sort the array\n\n2- store frequency of numbers in unordered_map\n\n3- iterate over the array and get the lower and upper bound of the range that after the operation can be = nums[i] for i = [0, n - 1] , the number of elements that need operation is range size - freq[nums[i]], minimize the need with numOfOperations and maximize the result + freq[nums[i]]\n\n4- maximize the result with the maximum range we can get from [1, numOfOperations] to perform operations on this range to have same number not in nums arrray\n\n5- perform binary search on answer from 1->numOfOperations, for each window size test if consists any window of this size that has boundaries [l, r] and nums[l] + k >= nums[r] - k, which means the range after performing the operations can be unified \n\n6- return the maximum between the 2 approaches\n\n\n# Complexity\n- Time complexity:O(N * log(N))\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    bool ok(int sz, vector<int>& nums, int k){\n        for(int i = 0;i < nums.size();i++){\n            if(i >= sz - 1){\n                int p = i - sz + 1;\n                if(nums[p] + k >= nums[i] - k)\n                    return true;\n            }\n        }\n        return false;\n    }\n\n    int maxFrequency(vector<int>& nums, int k, int numOperations) {\n        // lower bound on the ans\n        sort(nums.begin(), nums.end());\n        unordered_map<int,int> freq;\n        for(auto a: nums) freq[a]++;\n        // check max answer if the number to have most freq in nums\n        int ans = 1;\n        for(auto p: freq){\n            int a = p.first;\n            int l = lower_bound(nums.begin(), nums.end(), a - k) - nums.begin();\n            int r = upper_bound(nums.begin(), nums.end(), a + k) - nums.begin();\n            int turn = min(numOperations, r - l - freq[a]);\n            ans = max(ans, turn + freq[a]);\n        }\n\n        // if it\'s not in nums check max subarray can be changed\n        \n        int l = 1,r = numOperations, mid;\n        while(l <= r){\n            mid = (l + r) >> 1;\n            if(ok(mid, nums, k))\n                l = mid + 1, ans = max(ans, mid);\n            else\n                r = mid - 1;\n        }\n        return ans;\n    }\n};\n```
['Binary Search', 'C++']