# 1838. Frequency of the Most Frequent Element

{%hackmd theme-dark %}
The frequency of an element is the number of times it occurs in an array.

You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most k operations.

1 2 4, k = 5
1+3, 2+2, 4,

# op + < k
# len of array 10**5
# val all postive 1-1000
# no duplicate num
# non sorted
# k >=1

# [1+3 2+2 4] k=6 -> 4*3

# [1 2 3 4 5 6 7] k=3
# [1 2+2 3+1 4 5 6 7]

[1 2 3 4 5 6 7]
lo hi

def maxFrequency(self, nums: List[int], k: int) -> int:
    
    nums.sort()

    lo = 0    
    curSum = k # lo to i sum
    # 3
    ans = 0
    for i in range(len(nums)):
        # [1 2 3 4 5
        n = nums[i]
        curSum += n # 12+5 = 17
        curMax = n*(i-lo+1) # 5*(4-1+1) = 20
        while curMax > curSum: #20 > 17
            curSum -= nums[lo] # 17 - 2 = 15
            curMax -= n  # 20 - 5 = 15
            lo += 1 
        ans = max(ans, i-lo+1)
    
    return ans
            
            
        
        
        
        
    

###### tags: `mock interview` `面試`