[Golang] O(1) Space Complexity | No Prefix Sum | Binary Search | Sliding Window
Intuition\nThe first idea is that if we have an array of numbers and we want to make them all equal, selecting a median and equating all the other numbers to it
# Intuition\nThe **first idea** is that if we have an array of numbers and we want to make them all equal, selecting a median and equating all the other numbers to it will require the least amount of operations. And the fastest way to find the median is to sort the array and then for each subarray the median will be just the center element. \nThe **second idea** is that we can use a binary search to find the best possible score that we can achieve. \nOne **remaining question** is how to quikly check if the selected score can be achieved, and there is an effective algorithm for that - Sliding Window algorithm! We just need to fix the window length and then check if we can achieve the score with the operations cost sum less then k.\n\n# Approach\n- At first we sort the array. This will allow us to quickly find the median of the subarray, it will be just a center element\n- After this we start a binary search procedure, checking on each step if the selected score can be achieved. If it can be achieved - we move to the right, if not - to the left\n- To check if the score can be achieved we use a sliding window algorithm with the predefined length \n- At first we will prefill the sliding window and after this will start the sliding process \n- If at any step the operations cost of achieving the score is less then k, we return true, we return false otherwise\n\n# Complexity\n- Time complexity: $$O(n \\cdot \\log\\,n)$$ \n\n- Space complexity: $$O(1)$$\n\n# Code\n```\nfunc maxFrequencyScore(nums []int, k int64) int {\n    sort.Ints(nums)\n    \n    left := 0\n    right := len(nums) \n    result := 0\n    \n    for left < right {\n        mid := (left + right)/2\n        if canScore(nums, k, mid) {\n            left = mid + 1\n            result = max(result, mid)\n        } else {\n            right = mid\n        }\n    }\n    \n    if canScore(nums, k, left) {\n        result = max(result, left)\n    }\n    \n    return result\n}\n\nfunc canScore(nums []int, k int64, windowLength int) bool {\n    var cost int64 = 0\n    \n    mid := windowLength / 2\n    target := nums[mid]\n    for i := 0; i < windowLength; i++ {\n        cost += int64(abs(nums[i] - target))\n    }\n            \n    if (cost <= k) {\n        return true\n    }\n    \n    for right := windowLength; right < len(nums); right++ {\n        left := right - windowLength\n               \n        cost += int64(abs(nums[right] - nums[(left + right + 1) / 2]))\n        cost -= int64(abs(nums[left] - nums[(left + right) / 2]))\n        \n        if (cost <= k) {\n            return true\n        }\n    }\n    \n    return false\n}\n\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n\nfunc abs(a int) int {\n    if a < 0 {\n        return -a\n    }\n    return a\n}\n```
['Binary Search', 'Sliding Window', 'Sorting', 'Go']