[Python3/C++/Java] Sweep Line - Detail Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n- Each point we will have the range [point - k, point + k] that it can affects\n- The q
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Each point we will have the range `[point - k, point + k]` that it can affects\n- The question asking about the point which can have the most affected.\n- the range of points we should check should be from `[min_point - k, max_point + k]`.\n- For every point in this range we find the points with the most affected\n- It sounds like most accumulate points in range, so it is sweep line\n- for each point in the line, it can be affected by 2 kind of point:\n    - the point at this location itself\n    - other points`p` which the current point is in range `[p - k, p + k]`\n- Thus, it is a bit tricky than usual sweep line.\n- More Sweep Line Problem can be found [here](https://leetcode.com/problem-list/ms0edv4m/)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**1. Data Structures**:\n\n- `points_cover`: A Counter (dictionary-like object) to store the net change in the number of "covering intervals" at each point on the number line.\n- `cnt_points`: A Counter to store the frequency of each number in the input array nums.\n`points`: A set to store all unique numbers in nums as well as the endpoints of the intervals defined by `k`.\n\n**2. Building the Sweep Line**:\n\n- The code iterates through each `num` in `nums`.\n    - It increments the count of `num` in `cnt_points`.\n    - For each `num`, it creates a "covering interval" of `[num - k, num + k]`.\n    - To represent this interval on the sweep line:\n        - It increments `points_cover` at `num - k` (start of the interval).\n        - It decrements points_cover at `num + k + 1` (end of the interval + 1). This is because the interval is inclusive of `num + k`.\n        - It adds `num`, `num - k`, and `num + k + 1` to the `points` set.\n\n**3. Sweeping the Line**:\n\n- The code sorts the `points` in ascending order.\n- It iterates through the sorted points:\n    - `points_cover_this_point` tracks the cumulative sum of `points_cover` up to the current point. This essentially tells us how many intervals are "active" or "covering" the current `point`.\n    - For each point, it calculates the maximum frequency achievable at that point. This is done by taking the original count of the `point` `cnt_points[point]` and adding the minimum of the number of active intervals covering this point minus the original count of the point `points_cover_this_point - cnt_points[point]` . This represents how many times we can increment the point using the available operations within the k constraint - The total allowed operations (numOperations).\n    - It updates the `res` (result) to store the maximum frequency found so far.\n\n**4. Return Result**:\n\n- The code returns the res, which holds the maximum frequency achieved after the sweep line process.\n\nIn essence, the sweep line approach helps to efficiently determine how many numbers can be incremented to a certain value while staying within the `k` constraint and the limit of `numOperations`. By processing the points in sorted order, it keeps track of the active intervals and calculates the maximum frequency at each point.\n\n**Example**:\n\nLet\'s say nums = [1, 4, 8, 13], k = 5, and numOperations = 2.\n\n- The code will create intervals like [1-5, 1+5], [4-5, 4+5], etc.\n- The points set will contain {-4, 1, 6, -1, 4, 9, 3, 8, 13, 18}.\n- During the sweep, at point 4, it will find that it\'s covered by two intervals ([1-5, 1+5] and [4-5, 4+5]).\n- It can use the numOperations to increment the frequency of 4 by 2 (within the constraint of k).\n- This approach efficiently finds the maximum frequency achievable after the allowed operations.\n\n# Complexity\n- Time complexity: $$O(NlogN)$$ - `N` number of possible points\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```python3 []\nclass Solution:\n    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:\n        points_cover = collections.Counter()\n        cnt_points = collections.Counter()\n        points = set()\n        for num in nums:\n            cnt_points[num] += 1\n            points_cover[num - k] += 1\n            points_cover[num + k + 1] -= 1\n            points.update({num, num - k, num + k + 1})\n        res = points_cover_this_point = 0\n        for point in sorted(points):\n            points_cover_this_point += points_cover[point]\n            res = max(res, cnt_points[point] + \n                        min(points_cover_this_point - cnt_points[point], numOperations))\n        return res\n```\n``` C++ []\nclass Solution {\npublic:\n    int maxFrequency(vector<int>& nums, int k, int numOperations) {\n        unordered_map<int, int> points_cover;\n        unordered_map<int, int> cnt_points;\n        set<int> points;\n\n        for (int num : nums) {\n            cnt_points[num]++;\n            points_cover[num - k]++;\n            points_cover[num + k + 1]--;\n            points.insert(num);\n            points.insert(num - k);\n            points.insert(num + k + 1);\n        }\n\n        int res = 0;\n        int points_cover_this_point = 0;\n\n        for (int point : points) {\n            points_cover_this_point += points_cover[point];\n            res = max(res, cnt_points[point] + \n                        min(points_cover_this_point - cnt_points[point], numOperations));\n        }\n\n        return res;\n    }\n};\n```\n``` java []\nclass Solution {\n    public int maxFrequency(int[] nums, int k, int numOperations) {\n        Map<Integer, Integer> pointsCover = new HashMap<>();\n        Map<Integer, Integer> cntPoints = new HashMap<>();\n        Set<Integer> points = new TreeSet<>(); // TreeSet to keep points sorted\n\n        for (int num : nums) {\n            cntPoints.put(num, cntPoints.getOrDefault(num, 0) + 1);\n            pointsCover.put(num - k, pointsCover.getOrDefault(num - k, 0) + 1);\n            pointsCover.put(num + k + 1, pointsCover.getOrDefault(num + k + 1, 0) - 1);\n            points.add(num);\n            points.add(num - k);\n            points.add(num + k + 1);\n        }\n\n        int res = 0;\n        int pointsCoverThisPoint = 0;\n\n        for (int point : points) {\n            pointsCoverThisPoint += pointsCover.getOrDefault(point, 0);\n            res = Math.max(res, cntPoints.getOrDefault(point, 0) + \n                        Math.min(pointsCoverThisPoint - cntPoints.getOrDefault(point, 0), numOperations));\n        }\n\n        return res;\n    }\n}\n```
['Array', 'Hash Table', 'Line Sweep', 'Sorting', 'Prefix Sum', 'C++', 'Java', 'Python3']