Range concept O(n) solution || Beats 100%
Approach\n1. maxFrequency approach leverages prefix sums and frequency counting over an ordered map structure, which enables efficient traversal of distinct key
# Approach\n1. maxFrequency approach leverages prefix sums and frequency counting over an ordered map structure, which enables efficient traversal of distinct key values in O(N) time complexity\n\n# Initialize Ordered Maps for Ranges and Frequencies\n\n1. range: Tracks the effect of adding or removing values at each specific key position.\n2. freq: Tracks the actual frequency of each number in the input nums.\nDetermine Range of Influence and Set Boundaries\n\n1. For each num in nums, calculate the left (l) and right (r) bounds where its influence would apply if we could increment or decrement it by up to k.\n2. Adjust minrange and maxrange to represent the smallest and largest bounds across all elements.\n# Populate range:\n1. range[l]++ to mark the start of influence at l.\n2. range[r + 1]-- to mark the end of influence at r + 1.\n3. range[nums[i]] += 0 initializes the key for every nums[i] in the map to ensure it exists when we later calculate cumulative sums.\n# Calculate Cumulative Influence Using Prefix Sum\n\n1. Traverse range in ascending order of keys. For each key it, calculate cumulative influence by adding the previous cumulative sum (lastsum) to range[it]. Update lastsum to reflect this cumulative sum.\n# Determine Maximum Frequency Achievable\n\n1. For each key it, calculate:\nmaxfreq as the cumulative influence (it->second) minus the frequency of the key (freq[it->first]).\n2. maxfreq = min(maxfreq, numOperations) to ensure we don\u2019t exceed the allowed number of operations.\n3. Update ans with the maximum of freq[it->first] + maxfreq for each key, which represents the highest achievable frequency for that number.\n# Return the Result\n\n1. ans will hold the maximum frequency we can achieve with up to numOperations increments/decrements.\n\n# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(N)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxFrequency(vector<int>& nums, int k, int numOperations) {\n        map<int,int>range;\n        map<int,int>freq;\n\n        int minrange=2*1e9;\n        int maxrange=-2*1e9;\n\n        for(int i=0;i<nums.size();i++){\n            freq[nums[i]]++;\n            int l=nums[i]-k;\n            int r=nums[i]+k;\n\n            minrange=min(minrange,l);\n            maxrange=max(maxrange,r);\n            range[l]++;\n            range[r+1]--;\n            range[nums[i]]+=0;\n        }\n\n        int ans=1;\n        int lastsum=0;\n        for(auto it=range.begin();it!=range.end();it++){\n            it->second+=lastsum;\n            lastsum=it->second;\n            int maxfreq=it->second-freq[it->first];\n\n            maxfreq=min(maxfreq,numOperations);\n            ans=max(ans,freq[it->first]+maxfreq);\n        }\n\n        return ans;\n    }\n};\n```\n```java []\nimport java.util.HashMap;\n\nclass Solution {\n    public int maxFrequency(int[] nums, int k, int numOperations) {\n        HashMap<Integer, Integer> range = new HashMap<>();\n        HashMap<Integer, Integer> freq = new HashMap<>();\n\n        int minrange = (int) 1e9;\n        int maxrange = (int) -1e9;\n\n        for (int num : nums) {\n            freq.put(num, freq.getOrDefault(num, 0) + 1);\n            int l = num - k;\n            int r = num + k;\n\n            minrange = Math.min(minrange, l);\n            maxrange = Math.max(maxrange, r);\n            range.put(l, range.getOrDefault(l, 0) + 1);\n            range.put(r + 1, range.getOrDefault(r + 1, 0) - 1);\n        }\n\n        int ans = 1;\n        for (int i = minrange; i <= maxrange; i++) {\n            range.put(i, range.getOrDefault(i - 1, 0) + range.getOrDefault(i, 0));\n            int cnt = freq.getOrDefault(i, 0);\n            int maxfreq = range.get(i) - cnt;\n            maxfreq = Math.min(maxfreq, numOperations);\n            ans = Math.max(ans, cnt + maxfreq);\n        }\n\n        return ans;\n    }\n}\n\n```\n```python []\nfrom collections import defaultdict\n\nclass Solution:\n    def maxFrequency(self, nums, k, numOperations):\n        range_map = defaultdict(int)\n        freq = defaultdict(int)\n\n        minrange = int(1e9)\n        maxrange = -int(1e9)\n\n        for num in nums:\n            freq[num] += 1\n            l = num - k\n            r = num + k\n\n            minrange = min(minrange, l)\n            maxrange = max(maxrange, r)\n            range_map[l] += 1\n            range_map[r + 1] -= 1\n\n        ans = 1\n        for i in range(minrange, maxrange + 1):\n            range_map[i] += range_map[i - 1]\n            cnt = freq[i]\n            maxfreq = range_map[i] - cnt\n            maxfreq = min(maxfreq, numOperations)\n            ans = max(ans, cnt + maxfreq)\n\n        return ans\n\n```\n```javascript []\nfunction maxFrequency(nums, k, numOperations) {\n    const range = new Map();\n    const freq = new Map();\n\n    let minrange = 1e9;\n    let maxrange = -1e9;\n\n    for (const num of nums) {\n        freq.set(num, (freq.get(num) || 0) + 1);\n        const l = num - k;\n        const r = num + k;\n\n        minrange = Math.min(minrange, l);\n        maxrange = Math.max(maxrange, r);\n        range.set(l, (range.get(l) || 0) + 1);\n        range.set(r + 1, (range.get(r + 1) || 0) - 1);\n    }\n\n    let ans = 1;\n    for (let i = minrange; i <= maxrange; i++) {\n        range.set(i, (range.get(i - 1) || 0) + (range.get(i) || 0));\n        const cnt = freq.get(i) || 0;\n        let maxfreq = range.get(i) - cnt;\n        maxfreq = Math.min(maxfreq, numOperations);\n        ans = Math.max(ans, cnt + maxfreq);\n    }\n\n    return ans;\n}\n\n```\n![c2d27b08-ffbe-4bc6-8b29-5fc4d8effd5f_1723775276.9029489.jpeg](https://assets.leetcode.com/users/images/1be32bc8-156c-4f4c-a65f-0fcce6083bba_1731177957.0711734.jpeg)\n\n
['Dynamic Programming', 'Greedy', 'Ordered Map', 'Prefix Sum', 'C++', 'Java', 'Python3', 'JavaScript']