TreeMap and Line Sweep Algo for bigger input (10^9)
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem statement focuses on intervals, so line sweep algorithm felt like a good ch
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem statement focuses on intervals, so line sweep algorithm felt like a good choice.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nStore the nums[i] - k and nums[i] + k in the tree map, which will be sorted with respect to nums itself. Also, store the value of nums[i] into the tree map so that we don\'t miss the case of nums[i] when sweeping the line via tree map.\n\nfinally, while sweeping take the min of num operations and sweep accumilated till this num.\n\nEdge case: Do consider subtracting the freq of a num from sweep, since that will prevent us to use the num opertions.\n\n# Complexity\n- Time complexity: O(nlog(n))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int maxFrequency(int[] nums, int k, int numOperations) {\n        Map<Long, Long> arrMap = new TreeMap<>();\n        Map<Long, Long> freq = new HashMap<>();\n        int n = nums.length;\n        for(int i = 0;i < n; i++) {\n            freq.put((long)nums[i], freq.getOrDefault((long)nums[i], 0L) + 1);\n            long left = Math.max(0, nums[i] - k);\n            arrMap.put(left, arrMap.getOrDefault(left, 0L) + 1);\n            long right = nums[i] + k + 1;\n            arrMap.put(right, arrMap.getOrDefault(right, 0L) - 1);\n            arrMap.put((long)nums[i], arrMap.getOrDefault((long)nums[i], 0L));\n        }\n        long max = 1;\n        long sweep = 0;\n        for(Map.Entry<Long, Long> entry : arrMap.entrySet()) {\n            sweep += entry.getValue();\n            long fre = sweep - freq.getOrDefault(entry.getKey(), 0L);\n            max = Math.max(max, Math.min(fre, numOperations) + freq.getOrDefault(entry.getKey(), 0L));\n        }\n        return (int)max;\n    }\n}\n```
['Java']