2779. Maximum Beauty of an Array After Applying Operation

link

Method 1

First thought, but when seeing the data, know it's TLE O(n^2) dataset 10^5

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        
        n = len(nums)
        
        M = defaultdict(int)
        
        
        for i in range(n):
            num = nums[i]
            M[num] += 1
            for j in range(1, k+1):
                M[num+j] += 1
                M[num-j] += 1
                
        return max(M.values())

Method 2

Silde window with limitation

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        
        n = len(nums)
        
        c = Counter(nums)
        
        arr = list(c.items())
        arr.sort(key=lambda x:x[0])
        
        l = 0
        
        current = 0
        res = 0
        for i in range(len(arr)):
            
            current += arr[i][1]
            
            while arr[i][0] - arr[l][0] > 2 * k:
                current -= arr[l][1]
                l += 1
            
            res = max(res, current)
            
        return res