Course4all

Frequency of the Most Frequent Element

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Sliding Window.

Frequency of the Most Frequent Element

Maximize the frequency of an element by incrementing other elements by at most k overall.

Visual Representation

nums = [1, 2, 4], k = 5 Sort: [1, 2, 4] Window [1, 2, 4] ending at 4: Cost to make all 4: (4-1) + (4-2) + (4-4) = 3 + 2 + 0 = 5 Cost 5 <= k (5)? YES! Frequency = 3
Medium

Examples

Input: nums = [1,2,4], k = 5
Output: 3
Approach 1

Level I: Brute Force

Intuition

For each element x in the array, try to make a sequence of elements equal to x ending at x. Use a sliding window to find the maximum possible frequency for each starting position.

Thought Process

  1. Sort the array.
  2. Iterate i from 0 to n-1.
  3. Iterate j from i to n-1.
  4. Calculate cost = sum(nums[j] - nums[k]) for k in [i...j].
  5. If cost <= k, maxFreq = max(maxFreq, j - i + 1).
⏱ O(N^2)💾 O(1)

Detailed Dry Run

ijWindowCostMax Freq
00[1]01
01[1, 2](2-1) = 12
02[1, 2, 4](4-1)+(4-2) = 53
java
import java.util.*;
public class Main {
    public static int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, maxFreq = 1;
        for (int i = 0; i < n; i++) {
            long cost = 0;
            for (int j = i + 1; j < n; j++) {
                cost += (long)(j - i) * (nums[j] - nums[j-1]);
                if (cost <= k) maxFreq = Math.max(maxFreq, j - i + 1);
                else break;
            }
        }
        return maxFreq;
    }

    public static void main(String[] args) {
        System.out.println(maxFrequency(new int[]{1, 2, 4}, 5)); // 3
    }
}
Approach 2

Level II: Binary Search on Answer (O(N log N))

Intuition

After sorting, we can binary search for the maximum frequency L. For a fixed L, we check if any subarray of length L exists such that the cost to make all elements equal to the largest element in that subarray is ≤k\le k.

Thought Process

  1. Sort the array.
  2. Search range for frequency L is [1, n].
  3. For each mid length:
    • Use a fixed-size sliding window of size mid.
    • Cost for window [i, i + mid - 1] is nums[i + mid - 1] * mid - windowSum.
    • If any window has cost <= k, mid is possible.
  4. Adjust the search range accordingly.

Pattern: BS on Answer + Rolling Sum

⏱ O(N log N) - Sorting takes $O(N \log N)$, and binary search check takes $O(N)$ for each of the $\log N$ steps.💾 O(1) - Ignored sorting space.
java
public class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int low = 1, high = nums.length, ans = 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(nums, k, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean check(int[] nums, int k, int len) {
        long currentSum = 0;
        for (int i = 0; i < nums.length; i++) {
            currentSum += nums[i];
            if (i >= len) currentSum -= nums[i - len];
            if (i >= len - 1) {
                long cost = (long)nums[i] * len - currentSum;
                if (cost <= k) return true;
            }
        }
        return false;
    }
}
Approach 3

Level III: Optimal (Sorting + Sliding Window)

Intuition

Thought Process

After sorting, for any window [left, right], it's always optimal to make all elements equal to the largest element nums[right]. The total cost is nums[right] * windowSize - windowSum. We maintain the largest possible window that satisfies cost <= k.

Patterns

  1. Sort then Window: Sorting allows monotonic cost calculations.
  2. Sum-based Cost: cost = lastVal * len - sum.
⏱ O(N log N)💾 O(1)

Detailed Dry Run

RNumSumCost (4*Win - Sum)Max Freq
01101
1232*2 - 3 = 12
2474*3 - 7 = 53
java
import java.util.*;
public class Main {
    public static int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0, res = 1;
        long sum = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while ((long)nums[right] * (right - left + 1) - sum > k) {
                sum -= nums[left++];
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(maxFrequency(new int[]{1, 2, 4}, 5));
    }
}

⚠️ Common Pitfalls & Tips

Integer overflow is a common issue here. nums[right] * (right - left + 1) can exceed 2^31 - 1, so use 64-bit integers (long in Java/C++, default in Python/JS) for intermediate calculations.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionSubarrays with K Different Integers
Next Question →Longest Substring with At Most K Distinct Characters