1838.-frequency-of-the-most-frequent-element.md

1838. Frequency of the Most Frequent Element

• Medium

• 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.

Analysis

This is part of DP and we can apply a technic called sliding window. Suppose we are looking at an consecutive subsequence in an array and we are trying to go through all of it. Then we are looking at something like this

But pay attention to what is changing during each move. Yes, only the start and the end is changed and the rest stays the same. Now, if we are looking for the , say, average of the subsequence, then for each move towards the end of the array, we only have to look at the new ending point and the point it has left out. Like this pic

Now thinking about this question. First we would like it to be sorted so that when we move our 'window' we know that the next one we are facing is larger.

Then, for each node, we can choose do the following things:

1. if the steps needed to add this node into the window is less than the steps remaining, then we add it.
2. If it is more than the remain, that is to say, we don't have enough steps to add it, we start to remove the points from the beginning until we have enough steps remain. Since we have an sorted array, we are sure that the ones in the beginning are the ones that need the most steps to achieve the same value.
3. For each addition, record the current length(end-start+1),if it is larger than the current maximum, then change the current maximum.
4. after we have went through all the nodes, we will have the maximum. And since we are only going through the array once, the time complexity for this part would be O(n)

Solution (O(sorting) / O(n log n))

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        start,end=0,0
        remain=k
        maxi=1
        currlen=1
        for i in range(1,len(nums)):
            need=(nums[i]-nums[end])*currlen
            while need>remain and start<=end:
                remain+=nums[i]-nums[start]
                start+=1
                currlen-=1
            if need<=remain:
                end+=1
                currlen+=1
                maxi=max(maxi,currlen)
                remain=remain-need
            print(start,end,need,remain)
        return maxi

To be honest, the method to calculate the need used above is not smart at all. Now think about this, if we want to fill several cups with different amout of water in it, all we need to calculate the water needed is the total capacity of the cups and the total of current amount of water in it.

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        i=0
        maxi=1
        for j in range(len(nums)):
            k+=nums[j]
            while k<nums[j]*(j-i+1):
                k-=nums[i]
                i+=1
            maxi=max(maxi,j-i+1)
        return maxi

Now can we remove the 'while' loop?

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        i=0

        for j in range(len(nums)):
            k+=nums[j]
            if k<nums[j]*(j-i+1):
                k-=nums[i]
                i+=1
        #we are starting at an window of width, therefore we are growing the window size as we go 
        #suppose there is one node that can be add to the window without removing an previous node, then the window size has grown
        #Now as soon as we have a window of size two available, we won't care about windows of size 1. Therefore we are not removing mulitple nodes. 
        # If the new node fits, then the window grows. If it doesn't fit, then the window stays the same size until we find an node that fits. 
        #Therefore even though the window we end up in the end might not satisfy the requirement, we are sure that there is at least one window of the same size in the array.
        
        return j-i+1