1838. Frequency of the Most Frequent Element - cocoder39/coco39_LC GitHub Wiki

1838. Frequency of the Most Frequent Element

Option 1: Sliding window

range_sum + k >= len(range) * max_in_range then k operations could make all items in the window to be identical. The problem is now converted to sliding window

range_sum + k < len(range) * max_in_range -> sum(max_in_range - nums[i]) > k -> shrink the window

O(N log N) sort and O(N) in for-loop

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        total = k
        left = 0
        res = 0
        for i, num in enumerate(nums):
            total += num
            while total < num * (i-left+1):
                total -= nums[left]
                left += 1
            res = max(res, i-left+1)
        return res

Option 2: Binary search

O(N log N) sort and O(NlogN) in for-loop

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        
        sum_ = 0
        sums = []
        for num in nums:
            sum_ += num
            sums.append(sum_)
        
        def getFreq(index, target):
            low = 1
            high = index + 1
            while low + 1 < high:
                mid = low + (high - low) // 2
                if mid * target - sums[index] + (sums[index-mid] if index >= mid else 0) <= k:
                    low = mid
                else:
                    high = mid
            if high * target - sums[index] + (sums[index-high] if index >= high else 0) <= k:
                return high
            if low * target - sums[index] + (sums[index-low] if index >= low else 0) <= k:
                return low
            return -1
        
        res = 0
        for i, num in enumerate(nums):
            res = max(res, getFreq(i, num))
        return res