Intuitive C++ constant space Solution | O(nlogn) | Sorting + Binary Search
Intuition\nThe problem revolves around maximizing the frequency of a number in the array after performing a limited number of operations. The initial thought is
# Intuition\nThe problem revolves around maximizing the frequency of a number in the array after performing a limited number of operations. The initial thought is to focus on maximizing the count of an existing number in the array by utilizing the operations to transform other numbers into the target number.\n\nSorting the array enables us to use efficient binary search techniques to identify ranges of numbers that can be converted to the target within the allowable range of operations.\n\nHowever, a critical realization is that the number with the maximum achievable frequency does not necessarily have to exist in the original array. This insight expands the solution to consider target numbers that fall within the range of operations but are not necessarily present in the array.\n\n# Approach\n > I got a reasonable beats `97.73%` in Runtime & `96.66%` in Memory. Hopefully making this an optimal solution (although these numbers in leetcode do tend to vary a bit :p).\n### Part 1: The Naive Range\n1. Sort the array\n2. Iterate over the array:\n    - Consider current element `x` as the target to which we\'ll try and convert other number to using provided operations.\n    - These element would fall in the range [`x-k`, `x+k`]\n    - Given that the array is sorted, we could find numbers satisfying these extremes on either side of the current one using binary search efficiently.\n    - This calculation should then return us a window of size `ws`.\n    - Elements in the window which are already `==x` don\'t need any conversion. Hence, for a number we iterate to its right and get a count of all its reccurences `count_same_x` (storing this for later to skip all of these numbers).\n    - Thus, giving us the final count of `ws - count_same_x` elements to convert using provided operations. \n    - Finally, our answer falls down to two cases\n        - If `ws - count_same_x` is less than `num_ops` we get the max acheivable frequency for current element to be `ws`.\n        - If not, our max acheivable frequency becomes limited to `num_ops + count_same_x` (as elements which are already equal to target don\'t need conversion).\n\n### Part 2: Handling Missing Targets\n\n> Sigh, so apparently that should solve it right? Nope. Sadly the assumption that the element with the highest acheivable frequency should exist in the initial array isn\'t always true. So what do we do now?\n\n> Lets step back a bit. We are essentially finding ranges right? Assuming target element to be `x`, we get the range [`x-k`, `x+k`]. (The smallest element in this range being `x-k`) Given that the array is sorted, each element in left to right iteration is smaller than all elements to its right. Hence, considering current element `a` as `x-k`, we could find the right bound of our target range (`x+k`) by doing `a + 2*k`.\n\n> There you go! now we have a way to discover window sizes for target elements which might not even exist in our array! \n3. In the same iteration as above, also consider the following window for each element `a`:\n    - [`a`, `a + 2*k`]. (we can optimally find the index satisfying rightbound by binary search in the array to the right of `a`)\n    - Again, for this window, if the window size exceeds the number of ops, we would only be able to consider `num_ops` elements. (assuming, we apply ops to all elements.)\n\n> Remember that the operation of addition with 0 is possible as stated in question. So even if an element in the window already exists in the array. We can still count it in ops.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O($n \\log n$)\nSorting the array takes O($n \\log n$).\nEach iteration performs a binary search (avg O($n \\log n$)) and some linear operations to calculate counts.\n\n- Space complexity: O($1$)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxFrequency(vector<int>& nums, int k, int numOperations) {\n        // Step 1: Sort the array to enable binary search and range calculations\n        sort(nums.begin(), nums.end());\n\n        int n = nums.size();\n\n        // Binary search helper to find the leftmost valid index for range [x-k, x+k]\n        auto bsLeft = [&nums, k](int idx) {\n            int m, l = 0, r = idx - 1;\n            int res = -1; // Initialize to an invalid index\n\n            while (l <= r) {\n                m = l + (r - l) / 2;\n                // Check if nums[m] falls within the valid range\n                if (nums[m] >= nums[idx] - k) {\n                    res = m; // Update result and shrink range to the left\n                    r = m - 1;\n                } else {\n                    l = m + 1; // Move to the right\n                }\n            }\n\n            return res; // Return the leftmost valid index\n        };\n\n        // Binary search helper to find the rightmost valid index for range [x-k, x+k]\n        // The second argument will make sense in a while. Read the solution till the end.\n        auto bsRight = [&nums, n, k](int idx, bool exist) {\n            int m, l = idx + 1, r = n - 1;\n            int res = -1; // Initialize to an invalid index\n\n            int t = k; // Range adjustment factor\n            long long h;\n            if (!exist) t = 2 * k; // Expand range for missing targets\n\n            while (l <= r) {\n                m = l + (r - l) / 2;\n                h = nums[idx];\n                h += t;\n\n                // Check if nums[m] falls within the valid range\n                if (nums[m] <= h) {\n                    res = m; // Update result and expand range to the right\n                    l = m + 1;\n                } else {\n                    r = m - 1; // Shrink range to the left\n                }\n            }\n\n            return res; // Return the rightmost valid index\n        };\n\n        int res = 1; // Initialize the result to the minimum possible frequency\n        int smc, ws, l, r, fr;\n\n        // Step 2: Iterate through each element in the sorted array\n        for (int i = 0; i < n; i++) {\n            // Case 1: Target element exists in the array\n            l = bsLeft(i);  // Find the left bound\n            r = bsRight(i, true); // Find the right bound for `x+k`\n            fr = bsRight(i, false); // Find right bound for `a + 2*k`\n            \n            // Count occurrences of the current element\n            smc = 0;\n            for (int j = i; j < n; j++) {\n                if (nums[j] != nums[i]) break;\n                smc++;\n            }\n\n            // Calculate the window size for existing targets\n            ws = 1;\n            if (l != -1) ws += i - l; // Elements to the left\n            if (r != -1) ws += r - i; // Elements to the right\n\n            // Adjust based on the number of operations\n            if (ws - smc > numOperations) ws = numOperations + smc;\n            res = max(res, ws);\n\n            // Case 2: Target is created (not in original array)\n            ws = min(fr - i + 1, numOperations); // Constraint window size based on number of operations\n            res = max(res, ws);\n\n            // Skip duplicate elements\n            i += smc - 1;\n        }\n\n        return res; // Return the maximum achievable frequency\n    }\n};\n```
['Binary Search', 'Sorting', 'C++']