<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code> and an integer <code>k</code>.</p>

<p>You can perform the following operation on the array <strong>at most</strong> <code>k</code> times:</p>

<ul>
	<li>Choose any index <code>i</code> from the array and <strong>increase</strong> or <strong>decrease</strong> <code>nums[i]</code> by <code>1</code>.</li>
</ul>

<p>The score of the final array is the <strong>frequency</strong> of the most frequent element in the array.</p>

<p>Return <em>the <strong>maximum</strong> score you can achieve</em>.</p>

<p>The frequency of an element is the number of occurences of that element in the array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,6,4], k = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can do the following operations on the array:
- Choose i = 0, and increase the value of nums[0] by 1. The resulting array is [2,2,6,4].
- Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,3].
- Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,2].
The element 2 is the most frequent in the final array so our score is 3.
It can be shown that we cannot achieve a better score.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,4,4,2,4], k = 0
<strong>Output:</strong> 3
<strong>Explanation:</strong> We cannot apply any operations so our score will be the frequency of the most frequent element in the original array, which is 3.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= k &lt;= 10<sup>14</sup></code></li>
</ul>

class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        # For creating max freq of element, objective is to make all or most
        # of the elements of array same.
        # To make elements same, it is better if we choose any target value which is present
        # in the array. Because if we choose a target value which is not in array then,
        # more ops will be required.
        # Also, to make most of the element equal to target, we have to choose elements which are closest to target.
        # That means sorting is required to find elements adjacent to target. That means the group of elements which
        # are becoming equal to target must be continous around target. 

        # Choose all elements of array as potential target value

        """
        # brute force | O(n^2) | TLE
        # [1,4,4,2,4]
        # [1, 2, (4), 4, 4]
        # From the target, take the closest element either from left or right
        result = 0
        nums.sort()
        for i in range(len(nums)):
            count = 1
            ops = 0
            target = nums[i]
            target_left_idx = i - 1
            target_right_idx = i + 1
            while target_left_idx >= 0 and target_right_idx < len(nums):
                if abs(target - nums[target_left_idx]) < abs(target - nums[target_right_idx]):
                    ops += abs(target - nums[target_left_idx])
                    target_left_idx -= 1
                else:
                    ops += abs(target - nums[target_right_idx])
                    target_right_idx += 1
                if ops > k:
                    break
                count += 1

            while target_left_idx >= 0:
                ops += abs(target - nums[target_left_idx])
                target_left_idx -= 1
                if ops > k:
                    break
                count += 1
            
            while target_right_idx < len(nums):
                ops += abs(target - nums[target_right_idx])
                target_right_idx += 1
                if ops > k:
                    break
                count += 1

            result = max(result, count)
        return result
        """


        # Optimization: Since we have to check each and element of array as potential target, the outer for loop will surely be required
        # To check if elements can become target, we cant use binary search because the search required  at both sides of target
        # [1,2,4,6] if my target is 4 then we have to check both left and right element if they can become same as target
        # some elements of left can become target and some of left can become target which ever are more closer.
        # that means checking elements if they become equal to target within k ops also takes O(n) so overal O(n^2) only

        # Other way is to perform "binary search on answer"
        # Min freq can be 1 if all elements of array are unique
        # Max freq can be n if all elements of array are same
        # Now, we perform hit and try on different possible frequencies (1 to n) and take the largest one.
        # Here, freq means check if 'freq' no. of elements can become same within k ops.
        # Say if 'freq' is not possible then we wont check for higher frequencies.
        
        def is_possible(target_freq, prefix):
            # basicall need to find 'target_freq' elements which can become same
            # since the array is sorted, elements which can become same are contigious
            # So to run window of size 'target_freq' on the array to see if all elements of window
            # can become same within k ops
            # Say target_freq is 3 then on this array there will be following windows [(1,2,4),6] and [1,(2,4,6)]
            # Fixed length window
            # To check if all elements of window can become same then we have to choose a target value within the window
            # The best target value of the window would be the mid element
            # [1,2,4,6,8,12]
            # [1,2,4,6] prefix [1, 3, 7, 13]
            # [1,2,4,4,4]
            left = 0
            right = 0
            while right < len(nums):

                # Wait for window to form
                if right - left + 1 <  target_freq:
                    right += 1
                    continue

                target_idx = (left + right) // 2    # target is val to which all other elements have to reach to
                target = nums[target_idx]
                left_ops = abs((prefix[target_idx - 1] if target_idx - 1 >= 0 else 0) - (prefix[left -1] if left - 1 >= 0 else 0) - target * (target_idx - left))
                right_ops = abs(prefix[right] - prefix[target_idx] - target * (right - target_idx))
                if (left_ops + right_ops) <= k:
                    print(left, right)
                    return True

                # this wondow does not work, slide the window one position to right
                left += 1
                right += 1
            return False


        def prefix_sum():
            result = [nums[0]]
            for i in range(1, len(nums)):
                result.append(result[i - 1] + nums[i])
            return result

        nums.sort()
        start = 1
        end = len(nums)
        result = 1

        prefix = prefix_sum()
        while start <= end:
            mid = (start + end) // 2
            print(mid)
            if is_possible(mid, prefix):
                result = mid
                start = mid + 1
            else:
                end = mid - 1
        return result

        
1412