Frequency of the Most Frequent Element
- 2 min read
- LC-Medium
- Sliding Window
3 years ago
Solution
- Sort the array
- Maintain a sliding window
- The last element in the sliding window is the possible number that all other numbers that come before up try to sum up to. The key here is try
- Now, imagine a sliding window that has [1, 1, 1, 2], and our k is 4
- All the ones will try to add up to 2 so that we maximize the frequency
- If they do add up, our total sum would be the last element (2) multiplied by the sliding window length, 4, equaling 8
- We also keep track of the current running sum, which is 1 + 1 + 1 + 2 = 5
- If the possible sum minus current sum is less than or equal to k, we can do a possible conversion, so update your answer
- This number basically tells us how many times we do the increment calculation
- Possible sum is 8, and our current sum is 5, so we can increment 3 times, and that falls within k
- This answer is so simple it's stupid
| Time | Space | Explanation |
|---|---|---|
O(nlogn) | O(n) | Space used by sorting algorithm |
def maxFrequency(self, nums: List[int], k: int) -> int:
nums.sort()
l = running_sum = max_frequency = 0
for r in range(len(nums)):
running_sum += nums[r]
if (nums[r] * (r - l + 1)) - running_sum > k:
running_sum -= nums[l]
l += 1
max_frequency = max(max_frequency, r - l + 1)
return max_frequency