Most Efficient Algorithm: Beats 100% in TC (O(n log n)), SC (O(1))
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem asks us to determine the maximum frequency of a number that can be ac
![Screenshot 2024-11-10 041316.png](https://assets.leetcode.com/users/images/c7b955c7-5f8a-4c32-b4bd-c92cb7ab944a_1731193868.5461087.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem asks us to determine the maximum frequency of a number that can be achieved by performing at most a certain number of operations. An operation consists of incrementing or decrementing a number in the array by upto k, and we are allowed a limited number of operations ($$numOperations$$).\n\nOur goal is to figure out which number can appear the most after performing these operations, under the constraint that we cannot use more than the given number of operations. The strategy here is to sort the array and use binary search to efficiently calculate the possible transformations.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.  **Sorting the Array:**\n\n    By sorting the array first, we bring all identical elements together, making it easier to calculate how many times we can "expand" the current number to the left or right using the available operations.\n\n2.  **Binary Search for First and Last Occurrence:**\n\n    For each unique number, we want to calculate how many numbers around it can be converted to this number with the allowed operations. This is done using binary search. The function $$firstOccurance$$ helps find the first position of the current number in the sorted array. The function $$lastOccurance$$ helps find the last position of the current number in the sorted array. The positions of these occurrences are used to determine the frequency of the current number.\n\n3.  **Transforming Neighboring Numbers:**\n\n    To increase the frequency of a number, we can try to transform neighboring numbers into it. For example, if we are at number $$x$$ in the sorted array, we can check how many numbers in the range [$$x-k$$, $$x+k$$] can be transformed into $$x$$ using the allowed number of operations. The idea is to find a segment of numbers around $$x$$ that can be transformed into $$x$$ using the minimum number of operations. For this, we compute the number of operations needed to turn the numbers within this segment into $$x$$.\n\n4.  **Maximizing the Frequency:**\n\n    For each unique number in the sorted array, we calculate the maximum frequency that can be achieved by transforming neighboring numbers into it. This is done by considering:\n-   The frequency of the number itself (from $$firstOccurance$$ to $$lastOccurance$$).\n-   The number of operations available to transform neighboring numbers within a certain range into the current number.\nWe update the answer by keeping track of the maximum frequency found.\n\n5.  **Using a Sliding Window (Indirectly via Binary Search):**\n\n    While a direct sliding window might seem like a good approach, the large range of values **(10^9)** makes it **infeasible**. Instead, we use binary search on the numbers and keep track of the potential transformations, ensuring we respect the operation limit.\n\n6.  **Final Output:**\n\n    The maximum frequency found during the loop is the $$answer$$, which represents the maximum number of times any number can appear after at most numOperations operations.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(nlogn)$$ due to sorting and the binary search operations for each element in the array.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$, as we are only using a few additional variables and not requiring extra space like memoization tables\n# Code\n```cpp []\nclass Solution {\n    // Function to find the last occurrence of a target in the sorted array\n    int lastOccurance(vector<int>& nums, int target) {\n        int left = 0, right = nums.size() - 1;\n        \n        // Binary search to find the last occurrence of target\n        while (left <= right) {\n            int mid = (left + right) / 2;\n            if (nums[mid] == target) {\n                // If mid equals target, move left boundary to mid + 1\n                left = mid + 1;\n            } else if (nums[mid] > target) {\n                // If mid value is greater than target, reduce the right boundary\n                right = mid - 1;\n            } else {\n                // If mid value is less than target, increase the left boundary\n                left = mid + 1;\n            }\n        }\n        \n        // Return the last index where the target occurs\n        return left - 1;\n    }\n\n    // Function to find the first occurrence of a target in the sorted array\n    int firstOccurance(vector<int>& nums, int target) {\n        int left = 0, right = nums.size() - 1;\n        \n        // Binary search to find the first occurrence of target\n        while (left <= right) {\n            int mid = (left + right) / 2;\n            if (nums[mid] == target) {\n                // If mid equals target, move the right boundary to mid - 1\n                right = mid - 1;\n            } else if (nums[mid] > target) {\n                // If mid value is greater than target, reduce the right boundary\n                right = mid - 1;\n            } else {\n                // If mid value is less than target, increase the left boundary\n                left = mid + 1;\n            }\n        }\n        \n        // Return the first index where the target occurs\n        return right + 1;\n    }\n    \npublic:\n    // Main function to calculate the maximum frequency of numbers that can be achieved\n    // after at most \'numOperations\' operations\n    int maxFrequency(vector<int>& nums, int k, int numOperations) {\n        // Sort the array to bring the same elements together\n        sort(nums.begin(), nums.end());\n        int ans = 0;\n        \n        // Iterate through each number in the sorted array\n        for (int i = 0; i < nums.size(); i++) {\n            \n            // Only process if the current number is different from the previous number\n            if (i == 0 || nums[i] != nums[i - 1]) {\n                \n                // Find the first and last occurrences of the current number\n                int curLastOcc = lastOccurance(nums, nums[i]);\n                int curFirstOcc = firstOccurance(nums, nums[i]);\n                \n                // Calculate the number of available frequencies within the range\n                int freqAvail = lastOccurance(nums, nums[i] + k) - curLastOcc + curFirstOcc - firstOccurance(nums, nums[i] - k);\n                \n                // Update the answer with the maximum frequency after performing operations\n                ans = max(ans, curLastOcc - curFirstOcc + 1 + min(freqAvail, numOperations));\n                \n                // Consider the possibility of transforming to the next number within the range\n                ans = max(ans, min(lastOccurance(nums, nums[i] + 2ll * k) - curFirstOcc + 1, numOperations));\n            }\n        }\n        \n        // Return the maximum achievable frequency\n        return ans;\n    }\n};\n\n\n```\n\nP.S. I tried to use dp so that i don\'t have to find multiple time if current target\'s first or last occurance is but it takes so much overhead that both time and space shoot up so its better this way only
['Array', 'Binary Search', 'Greedy', 'Sliding Window', 'Sorting', 'C++']