3346. Maximum Frequency of an Element After Performing Operations I (Array, Binary Search, Sliding Window, Sorting, Prefix Sum)

링크 - https://leetcode.com/problems/maximum-frequency-of-an-element-after-performing-operations-i/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

Sliding window를 통해 풀 수 있는 문제이다. 먼저 nums에 대한 counter를 만든뒤, 그 keys들을 뽑아 unique한 num들만 만들고 그걸 sorting한다. 

그 다음, unique nums의 가장 작은 수부터, 가장 큰 수까지의 수를 1씩 올려가며 그걸 center number로 놓고 문제를 푼다. center number의 -k +k 범위의 unique nums들을 가지고 frequency를 구한 뒤, min(freq, num_counter.get(center_num, 0) + numOperatinos)를 통해 얼마나 많은 unique한 값들을 가질 수 있는 지 계산한다.

Code

class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
        ans = 0
        
        num_counter = Counter(nums)
        unique_nums = list(num_counter.keys())
        unique_nums.sort()

        freq = 0
        left = right = 0
        for center_num in range(unique_nums[0], unique_nums[-1] + 1):
            while right < len(unique_nums) and center_num + k >= unique_nums[right]:
                freq += num_counter[unique_nums[right]]
                right += 1
            while left < len(unique_nums) and center_num - k > unique_nums[left]:
                freq -= num_counter[unique_nums[left]]
                left += 1

            ans = max(ans, min(freq, num_counter.get(center_num, 0) + numOperations))

        return ans

Complexity

Time Complexity: O(KlogK + R) 여기서 K는 unique한 number들의 개수이고, R은 min num에서 max num까지의 길이이다.

Space Complexity: O(n) counter와 key값들 때문이다.