⚡Flashcard Drill➔
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

  1. Sort the array. In an optimal solution, the target element is the largest of a contiguous window that is raised to its value.
  2. For a window [l, r] whose maximum is nums[r], the cost to raise everything to nums[r] is nums[r] * (r - l + 1) - window_sum.
  3. Expand r and shrink l while the cost exceeds k.
  4. 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 >= k in the condition: at most k operations are allowed, so the window is invalid only when the cost exceeds k.
  • 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems