Frequency of the Most Frequent Element

Todo

Rewrite your code to match ectoplasmthedoc: https://pastebin.com/wG3SfY2h

• Doesn’t deal with < (n - 1) shenanigans

Todo

Change code to use binary search and also prefix sum

My First Solution

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        left = right = 0
        max_freq = 0
        freq = 1
 
        while right < (n - 1):
            if left > right:
                freq = 1
                right += 1
                continue
            
            # (the next element - current element) times the number of numbers that need to be changed to become that element
            allowance_needed = (nums[right + 1] - nums[right]) * (right - left + 1)
 
            if allowance_needed <= k:
                k -= allowance_needed
                freq += 1
                right += 1
            else:
                max_freq = max(max_freq, freq)
                k += nums[right] - nums[left]
                left += 1
                freq -= 1
            
        max_freq = max(max_freq, freq)
        return max_freq

---

References

https://leetcode.com/problems/frequency-of-the-most-frequent-element/