Line Sweep | Explained | Beats 100% time | Beats 100% space
\nThe Line Sweep algorithm is a way to find the maximum number of overlapping intervals, useful for many problems such as My Calendar II (recommended editorial)
\nThe Line Sweep algorithm is a way to find the maximum number of overlapping intervals, useful for many problems such as My Calendar II [(recommended editorial)](https://leetcode.com/problems/my-calendar-ii/editorial/#approach-2-line-sweep). It can be tweaked for this problem by also including the frequency of each actual number. The intervals in this case represent the range of values each number can be modified to by adding or subtracting up to k. For example, if a number in nums is 10 and k is 5, its interval is [5, 15].\n\nSortedDict is like a TreeMap in Java. It uses a binary search tree to keep its keys sorted, and it makes in-order traversal easy.\n\n# Code\n```python3 []\nfrom sortedcontainers import SortedDict\nclass Solution:\n    def maxFrequency(self, nums: List[int], num: int, numOperations: int) -> int:\n        up = [n + num for n in nums]  # upper limit for each number\n        down = [n - num for n in nums]  # lower limit for each number\n        dictionary = SortedDict()\n\n        # Add interval start and ends\n        for d in down:\n            dictionary[d] = dictionary.get(d, 0) + 1\n\n        for u in up:\n            # 0.1 is added so that two intervals starting and ending\n            # at the same number count as an overlap of 2 instead of just 1.\n            dictionary[u+0.1] = dictionary.get(u+0.1, 0) - 1\n\n        # Add the actual numbers and their frequencies, encoded with +0.01\n        for n in nums:\n            dictionary[n+0.01] = dictionary.get(n+0.01, 0) + 1\n\n        # Line sweep, searching for the maximum\n        overlapping_intervals = 0\n        answer = 0\n        for num, val in dictionary.items():\n            if abs(num - floor(num) - 0.01) < 0.01:  # num is an actual number in nums (ends in 0.01)\n                possible_nums = overlapping_intervals - val  # Number of nums that can be extended to this num\n                \n                # Only consider the current frequency of the current number (val)\n                # Plus as many extended numbers as numOperations allows\n                answer = max(answer, val + min(possible_nums, numOperations))\n\n            else:  # num is an extended version of a number in nums (ends in .0 or .1)\n                overlapping_intervals += val  # Part of line sweep, add or subtract current interval\n                answer = max(answer, min(overlapping_intervals, numOperations))  # Only consider as many overlapping intervals as numOperations allows\n\n        return answer\n```\n\n# Complexity\n- Time complexity: $$O(N)$$\n\n- Space complexity: $$O(N)$$
['Python', 'Python3']