Sliding Window — Frequency of the Most Frequent Element

↗ LeetCode: Frequency of the Most Frequent Element · Medium · pattern chapter →

Given nums and budget k (increments allowed), max frequency of any single value after operations.

Example 1 — nums=[1,2,4], k=5 → 3 (raise 1,2,4 to 4 → cost 3+2=5) Example 2 — nums=[1,4,8,13], k=5 → 2

Constraints — 1 ≤ n ≤ 10⁵; 1 ≤ k ≤ 10⁵. Brute enumeration of target values × window pairs is O(n²) = 10¹⁰ ops. Sort + sliding window is O(n log n) ≈ 1.7·10⁶.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Try every target value

Intuition. For each value v in nums, find the max count of elements we can raise to v with budget k. Sort; for each v, extend a window backward and sum costs.

int maxFrequencyBrute(int[] nums, int k) {
    Arrays.sort(nums);
    int best = 1;
    for (int r = 0; r < nums.length; r++) {
        long cost = 0;
        for (int l = r; l >= 0; l--) {
            cost += (long)(nums[r] - nums[l]);
            if (cost > k) break;
            best = Math.max(best, r - l + 1);
        }
    }
    return best;
}

Complexity — Time O(n²); Space O(1). At 10⁵ = 10¹⁰ ops = TLE. In an interview say "the inner scan is a window; sum can be maintained incrementally."

---

Approach 2 — Sort + sliding window with sum budget (canonical)

Insight. Sort. In window [l, r] of sorted nums, raising every value to nums[r] costs nums[r] * (r-l+1) - windowSum. Extend r; while cost > k, shrink l. Two pointers, O(n) after sort.

int maxFrequency(int[] nums, int k) {
    Arrays.sort(nums);
    long sum = 0;
    int l = 0, best = 0;
    for (int r = 0; r < nums.length; r++) {
        sum += nums[r];
        while ((long) nums[r] * (r - l + 1) - sum > k) sum -= nums[l++];
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Execution Trace

Sort + budget window — nums=[1,2,4], k=5

Complexity — Time O(n log n); Space O(1). Say aloud in an interview: "same sort+shrink template as Longest Repeating Character Replacement and Max Consecutive Ones III."

---

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Try every target	O(n²)	O(1)	Reference; TLE at 10⁵
Sort + sliding budget	O(n log n)	O(1)	Canonical

When to use which

• Sorted + monotone cost function → sliding budget.
• Decrement instead of increment → symmetric; sort and use different cost formula.
• Multiple target values → try each value as target with 2p.

✨AI Study CompanionBeta

Related problems

• Longest Repeating Character Replacement
• Minimum Operations to Reduce X to Zero
• Max Consecutive Ones III

Was this page helpful?