Frequency-Based Range Queries
Same solutions as 3346. Maximum Frequency of an Element After Performing Operations I\n\n\n\n---\n\n# Sliding Window\npython3 []\nclass Solution:\n    # O(nlogn
**Same solutions as [3346. Maximum Frequency of an Element After Performing Operations I](https://leetcode.com/problems/maximum-frequency-of-an-element-after-performing-operations-i/solutions/6125016/frequency-based-range-queries/)**\n\n\n\n---\n\n# Sliding Window\n```python3 []\nclass Solution:\n    # O(nlogn) time | O(n) space\n    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:\n        n = len(nums)\n        nums.sort()\n\n        freq = defaultdict(int)\n        for val in nums:\n            freq[val] += 1\n\n        left, right = 0, 0\n        res = 0\n\n        # making other numbers into val\n        for val in nums:\n            # right is exclusive\n            while right < n and nums[right] <= val + k:\n                right += 1\n\n            # left is inclusive\n            while left < right and nums[left] < val - k:\n                left += 1\n\n            numbers_in_range = right - left\n            already_was_val = freq[val]\n            can_make_val = min(numOperations, numbers_in_range - already_was_val)\n            new_val_freq = already_was_val + can_make_val\n            res = max(res, new_val_freq)\n\n        # making the given numbers into some value in between\n        left = 0\n        for right in range(n):\n            # left and right are both inclusive\n            while nums[left] + k < nums[right] - k:\n                left += 1\n            numbers_in_range = right - left + 1\n            can_make_val = min(numOperations, numbers_in_range)\n            new_val_freq = can_make_val\n            res = max(res, new_val_freq)\n\n        return res\n\n```\n\n---\n\n# Binary Search\n``` Python []\nclass Solution:\n    # O(nlogn) time | O(n) space\n    # n = length of nums\n    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:\n        n = len(nums)\n        nums.sort()\n\n        res = 0\n        for i in range(n):\n            if i > 0 and nums[i - 1] == nums[i]:\n                continue\n\n            val = nums[i]\n            freq = self.freq_after_converting_to_target(nums, val, k, numOperations)\n            res = max(res, freq)\n\n            mid_val = val + k\n            freq = self.freq_after_converting_to_target(nums, mid_val, k, numOperations)\n            res = max(res, freq)\n\n        return res\n\n    def freq_after_converting_to_target(self, sorted_nums, target, k, limit):\n        min_val, max_val = sorted_nums[0], sorted_nums[-1]\n        left, right = max(min_val, target - k), min(max_val, target + k)\n\n        target_first_idx = self.firstIndex(sorted_nums, target)\n        target_last_idx = self.lastIndex(sorted_nums, target)\n        upper_bound_last_idx = self.lastIndex(sorted_nums, right)\n        lower_bound_first_idx = self.firstIndex(sorted_nums, left)\n\n        numbers_in_range = upper_bound_last_idx - lower_bound_first_idx + 1\n        already_was_target = target_last_idx - target_first_idx + 1\n        can_be_target = min(limit, numbers_in_range - already_was_target)\n        new_val_freq = already_was_target + can_be_target\n        return new_val_freq\n\n    def firstIndex(self, nums, target) -> int:\n        left, right = 0, len(nums) - 1\n        res = right\n\n        while left <= right:\n            mid = (left + right) // 2\n            if nums[mid] < target:\n                left = mid + 1\n            elif nums[mid] >= target:\n                res = mid\n                right = mid - 1\n\n        return res\n\n    def lastIndex(self, nums, target) -> int:\n        left, right = 0, len(nums) - 1\n        res = left\n\n        while left <= right:\n            mid = (left + right) // 2\n            if nums[mid] <= target:\n                res = mid\n                left = mid + 1\n            elif nums[mid] > target:\n                right = mid - 1\n\n        return res\n```
['Array', 'Binary Search', 'Sliding Window', 'Sorting', 'Python3']