Python | Binary Search | No Prefix Sum | Understand -> Prove -> Implement | O(n log n) Time
Intuition\nWe first observe that this problem hints at a binary search type solution:\n- This is an optimization problem: we want the maximal ln such that we ca
# Intuition\nWe first observe that this problem hints at a binary search type solution:\n- This is an **optimization** problem: we want the **maximal** `ln` such that we can get `nums` to contain `ln` identical elements.\n- The value we are optimizing is **monotone**: if we can get `ln` identical elements we can get `l` identical elements for any `l < ln`.\n- Thus, if we can solve the problem: "Given `nums`, `k` and `ln`, determine if you can inc/dec elements in `nums` at most `k` times and get `ln` identical elements" **efficiently**, we can solve the original problem easily. As the maximal `ln` lies somewhere between `1` (which is always possible) and `n` (the number of elements in the list), we can find the maximal `ln` for which the answer is `True` with binary search on the interval $[1, n]$ (which will require $O(\\log n)$ iterations).\n\nThus, we have reduce our problem to the problem: Given `nums`, `k` and `ln`, determine if you can inc/dec elements in `nums` at most `k` times and get `ln` identical elements.\n\nNext, we observe some facts that will help us along the way:\n- Since this problem is order-agnostic and since it is "easier" to make close elements equal, we can sort `nums` before we begin. If we can achieve `ln` identical elements, there must be a sequence of `ln` adjacent elements (in the sorted list) that can be made equal.\n- Given a sequence of elements $A = \\{a_1 \\leq a_2, \\leq \\cdots \\leq a_{\\mathrm{ln}}\\}$ and an element $x$, the cost of modifying all elements in $A$ to $x$ is precisely $\\mathrm{Cost}(x) = \\sum_{a \\in A} |x-a|$. If we have no constraint on the choice of $x$ then it is known that choosing $x$ to be the median of $A$ minimizes the above cost [see here, for example](https://tommasorigon.github.io/StatI/approfondimenti/Schwertman1990.pdf).\n\nThus, our game plan is as follows: given (the sorted list) `nums`, `k` and `ln`, we will iterate over `nums` looking at `ln`-sized windows and compute the distance between the values in the window and their median. If at any point we reach a distance which is at most `k`, we will return `True` (if all windows are further than `k` from their median, we will return `False`). We then bisect to find the maximal `ln` as mentioned before.\n\n\n# Naive Approach\nThe algorithm we proposed earlier is straightforward to implement. Given a sequence $A$ and a value $x$, if we divide our sequence to $A_{\\leq x} = \\{a \\in A ~|~ a \\leq x\\}$ and $A_{> x} = \\{a \\in A ~|~ a > x\\}$, it is easy to verify that $\\mathrm{Cost}(x) = \\sum_{a \\in A} |x-a| = \\sum_{a \\in A_{\\leq x}} x-a + \\sum_{a \\in A_{>x}} a-x$.\n\nNext, if $x$ is the median then there are $\\ell = \\frac{\\mathrm{ln}}{2}$  elements in $A_{\\leq x}$ and in $A_{> x}$ (where we round down when `ln` is odd). It follows that the cost is $\\mathrm{Cost}(x) = \\sum_{a \\in A_{\\leq x}} x-a + \\sum_{a \\in A_{>x}} a-x$\n\nWe further simplify to get $\\mathrm{Cost}(x) = \\ell\\cdot x - \\left(\\sum_{a \\in A_{\\leq x}} a\\right) -x \\cdot \\ell +\\left( \\sum_{a \\in A_{>x}} a\\right) = \\sum_{a \\in A_{>x}} a-\\sum_{a \\in A_{\\leq x}} a$.\n\nThus, we can compute this cost for each sliding window of size `ln` and check if any of the windows have sum at most `k`, here is the implementation:\n```\nclass Solution:\n    def maxFrequencyScore(self, nums: List[int], k: int) -> int:\n        # Sort and init vars\n        nums.sort()\n        l, r = 1, len(nums)\n        res = 0\n        # Binary search maximal value mid where we can\n        # achieve max frequency mid using k inc/dec ops\n        while l <= r:\n            mid = (l+r) // 2 \n            # If mid is achieveable, update max and left side\n            if self.can_reach(nums, k, mid):\n                l = mid+1\n                res = max(res, mid)\n            # Otherwise update right side\n            else:\n                r = mid-1\n        return res\n\n    def can_reach(self, nums, k, ln):\n        n = len(nums)\n        for i in range(n - ln + 1):\n            # Compute cost of changing all numbers in windows of size ln\n            # starting at index i to their median\n            cost = sum(nums[i + ln - ln//2: i + ln]) - sum(nums[i: i + ln//2])\n            # If cost is at most k we are in range\n            if cost <= k: return True\n        return False\n```\nThe problem with this approach is of course the runtime. A single call to `can_reach` requires $O(n - \\mathrm{ln})$ iterations, each one taking $O(\\mathrm{ln})$ time. As $\\mathrm{ln} = \\frac{n}{2}$ in the first call to `can_reach`, this is already $O(n^2)$.\n\n# Improving the computation of $\\mathrm{Cost}(x)$\nTo speed up the process, assume we have computed the cost of a window `nums[0:ln]`, which we know to be `cost = sum(nums[ln-ln//2:ln]) - sum(nums[:ln//2])`. If `cost` is at most `k` we are done, otherwise, we proceed to the next window. To do so we need to "forget" about the first element `nums[0]`, add the *new* last element `nums[ln]` and modify the values in the window surrounding the median. The first two changes are easy:\n- Since `nums[0]` was in $A_{\\leq x}$ we need to increment the cost by `nums[0]`\n- Since `nums[ln]` is added to $A_{>x}$ we need to increment the cost by `nums[ln]`\nModifying the median values is a little trickier:\n- If `ln` is odd then we need to remove both the element before the median (since it as the median before and is now smaller than the median) and the median (since it was in $A_{>x}$ before and is now the median). These are the elements `nums[ln//2]` and `nums[ln//2 - 1]`.\n- If `ln` is even then the element succeeding the median switches from $A_{>x}$ to $A_{\\leq x}$ and thus we need to remove it twice (once for moving out of $A_{>x}$ and once for moving into $A_{\\leq x}$. This is element `nums[ln//2 - 1]`.\n\nThis modification allows us to move the window in $O(1)$ time and thus we can compute `can_reach` in $O(n)$ time for a single value of `ln`. We leave `maxFrequencyScore` unchanged and present only the modified `can_reach`:\n\n# Code\n```\ndef can_reach(self, nums, k, ln):\n    # Compute distance from median of first ln items\n    n = len(nums)\n    cost = sum(nums[ln - ln//2: ln]) - sum(nums[:ln//2])\n    if cost <= k: return True\n    \n    # Consider each consecutive ln elements\n    for i in range(1, n - ln + 1):\n        # Remove previously last item, add current first item\n        cost += nums[i + ln - 1] + nums[i - 1]\n        # If ln is even we need to remove the value after the median twice\n        if ln % 2 == 0:\n            cost -= 2*nums[i + ln//2 - 1]\n        # If it is odd, we need to remove the value before and after the median\n        else:\n            cost -= nums[i + ln//2]\n            cost -= nums[i + ln//2 - 1]    \n        # Check if we are in range\n        if cost <= k: return True\n    return False     \n```\n\n# Complexity\n- Time complexity: As we have just shown, `can_reach` runs in time $O(n)$. Sorting `nums` costs $O(n \\log n)$ time and bisecting the interval $[1, n]$ requires calling `can_reach` at most $\\log_2 n$ times, thus the total runtime is $O(n \\cdot \\log n)$\n\n- Space complexity: Sorting `nums` requires $O(n)$ space, given the list, `can_reach` requires only constant extra space for storing `cost`. The total space required is thus $O(n)$.\n\n
['Math', 'Binary Search', 'Sorting', 'Combinatorics', 'Python3']