NeetCode #233LC-1838MediumSliding Window
← Back to All Problems#233 · #1838 · Frequency of the Most Frequent Element(最高频元素的频数)
📌 Problem Statement & Constraints
The frequency of an element is the number of times it occurs. You can perform at most
k operations, each incrementing one element by 1. Return the maximum possible frequency of a single element. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^5, 1 <= k <= 10^5.💡 Core Algorithmic Approaches
- Sort the array. In an optimal solution, the target element is the largest of a contiguous window that is raised to its value.
- For a window
[l, r]whose maximum isnums[r], the cost to raise everything tonums[r]isnums[r] * (r - l + 1) - window_sum. - Expand
rand shrinklwhile the cost exceedsk. - The window length is the candidate frequency, and the answer is its maximum.
💻 Benchmark Python3 Implementation
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
nums.sort()
l = 0
cur = 0 # sum of the current window
best = 0
for r in range(len(nums)):
cur += nums[r]
# cost to raise the whole window to nums[r]
while nums[r] * (r - l + 1) - cur > k:
cur -= nums[l]
l += 1
best = max(best, r - l + 1)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort dominates; the window scan is O(n).
💾 Space Complexity
O(1) beyond the sort.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting to sort: the cost formula requires the window's maximum to be its rightmost element.
- Computing the cost as
nums[r] - nums[l]: the whole window must be raised, so the cost involves the sum. - Using
>= kin the condition: at mostkoperations are allowed, so the window is invalid only when the cost exceedsk. - Shrinking by more than one per step: the window should lose exactly one element to remain maximal.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner