1838. Frequency of The Most Frequent Element - Explanation

Description

The frequency of an element is the number of times it occurs in an array.

You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most k operations.

Example 1:

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

Output: 3

Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.

Example 2:

Input: nums = [1,4,8,13], k = 5

Output: 2

Explanation: There are multiple optimal solutions:

Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.

Constraints:

1 <= nums.length <= 100,000
1 <= nums[i], k <= 100,000

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - Arranging elements to enable efficient window-based approaches
Sliding Window - Maintaining a dynamic window with adjustable boundaries
Prefix Sum - Efficiently computing range sums for cost calculations
Binary Search - Finding optimal boundaries in sorted data
Greedy Reasoning - Understanding why the target value must exist in the original array

1. Brute Force

Intuition

We can only increment elements, so the target value for our frequent element must already exist in the array. For each element, we check how many smaller elements we can increment to match it using at most k operations.

Sorting the array helps because the elements closest in value to our target require the fewest increments. We greedily extend leftward from each position, incrementing elements until we run out of operations.

Algorithm

Sort the array in ascending order.
For each index i, treat nums[i] as the target value.
Starting from j = i - 1, work backward and subtract the cost nums[i] - nums[j] from a temporary budget.
Stop when the budget becomes negative.
The count of elements matching nums[i] is i - j.
Track and return the maximum count found in res.

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        res = 1
        for i in range(len(nums)):
            j = i - 1
            tmpK = k
            while j >= 0 and (tmpK - (nums[i] - nums[j])) >= 0:
                tmpK -= (nums[i] - nums[j])
                j -= 1
            res = max(res, i - j)
        return res

public class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int res = 1;

        for (int i = 0; i < nums.length; i++) {
            int j = i - 1;
            long tmpK = k;

            while (j >= 0 && (tmpK - (nums[i] - nums[j])) >= 0) {
                tmpK -= (nums[i] - nums[j]);
                j--;
            }
            res = Math.max(res, i - j);
        }
        return res;
    }
}

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int res = 1;

        for (int i = 0; i < nums.size(); i++) {
            int j = i - 1;
            long long tmpK = k;

            while (j >= 0 && (tmpK - (nums[i] - nums[j])) >= 0) {
                tmpK -= (nums[i] - nums[j]);
                j--;
            }
            res = max(res, i - j);
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    maxFrequency(nums, k) {
        nums.sort((a, b) => a - b);
        let res = 1;

        for (let i = 0; i < nums.length; i++) {
            let j = i - 1;
            let tmpK = k;

            while (j >= 0 && tmpK - (nums[i] - nums[j]) >= 0) {
                tmpK -= nums[i] - nums[j];
                j--;
            }
            res = Math.max(res, i - j);
        }
        return res;
    }
}

public class Solution {
    public int MaxFrequency(int[] nums, int k) {
        Array.Sort(nums);
        int res = 1;

        for (int i = 0; i < nums.Length; i++) {
            int j = i - 1;
            long tmpK = k;

            while (j >= 0 && tmpK - (nums[i] - nums[j]) >= 0) {
                tmpK -= (nums[i] - nums[j]);
                j--;
            }
            res = Math.Max(res, i - j);
        }
        return res;
    }
}

func maxFrequency(nums []int, k int) int {
    sort.Ints(nums)
    res := 1

    for i := 0; i < len(nums); i++ {
        j := i - 1
        tmpK := k

        for j >= 0 && tmpK-(nums[i]-nums[j]) >= 0 {
            tmpK -= nums[i] - nums[j]
            j--
        }
        if i-j > res {
            res = i - j
        }
    }
    return res
}

class Solution {
    fun maxFrequency(nums: IntArray, k: Int): Int {
        nums.sort()
        var res = 1

        for (i in nums.indices) {
            var j = i - 1
            var tmpK = k.toLong()

            while (j >= 0 && tmpK - (nums[i] - nums[j]) >= 0) {
                tmpK -= (nums[i] - nums[j])
                j--
            }
            res = maxOf(res, i - j)
        }
        return res
    }
}

class Solution {
    func maxFrequency(_ nums: [Int], _ k: Int) -> Int {
        let nums = nums.sorted()
        var res = 1

        for i in 0..<nums.count {
            var j = i - 1
            var tmpK = k

            while j >= 0 && tmpK - (nums[i] - nums[j]) >= 0 {
                tmpK -= nums[i] - nums[j]
                j -= 1
            }
            res = max(res, i - j)
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2 + n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

2. Prefix Sum + Binary Search

Intuition

Instead of extending leftward one element at a time, we can use binary search to find the optimal left boundary. The cost to make all elements in a range equal to the rightmost element is: (count * target) - sum_of_range. Using prefix sums, we compute range sums in O(1).

For each right boundary i, we binary search for the smallest left boundary m such that the cost is within budget k. The window size i - m + 1 gives us the frequency.

Algorithm

Sort the array and build a prefix sum array.
For each index i:
- Binary search for the leftmost index m where the cost (i - m + 1) * nums[i] - (prefix[i+1] - prefix[m]) is at most k.
- Update res with the window size.
Return the maximum frequency found.

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]

        res = 1
        for i in range(n):
            l, r = 0, i
            while l <= r:
                m = (l + r) // 2
                curSum = prefix_sum[i + 1] - prefix_sum[m]
                need = (i - m + 1) * nums[i] - curSum
                if need <= k:
                    r = m - 1
                    res = max(res, i - m + 1)
                else:
                    l = m + 1
        return res

public class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        int res = 1;
        for (int i = 0; i < n; i++) {
            int left = 0, right = i;
            while (left <= right) {
                int mid = (left + right) / 2;
                long curSum = prefixSum[i + 1] - prefixSum[mid];
                long need = (i - mid + 1) * 1L * nums[i] - curSum;
                if (need <= k) {
                    right = mid - 1;
                    res = Math.max(res, i - mid + 1);
                } else {
                    left = mid + 1;
                }
            }
        }
        return res;
    }
}

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<long long> prefixSum(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        int res = 1;
        for (int i = 0; i < n; ++i) {
            int l = 0, r = i;
            while (l <= r) {
                int m = (l + r) / 2;
                long long curSum = prefixSum[i + 1] - prefixSum[m];
                long long need = (i - m + 1) * 1LL * nums[i] - curSum;
                if (need <= k) {
                    r = m - 1;
                    res = max(res, i - m + 1);
                } else {
                    l = m + 1;
                }
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    maxFrequency(nums, k) {
        nums.sort((a, b) => a - b);
        const prefixSum = new Array(nums.length + 1).fill(0);
        for (let i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        let res = 1;
        for (let i = 0; i < nums.length; i++) {
            let left = 0,
                right = i;
            while (left <= right) {
                const mid = Math.floor((left + right) / 2);
                const curSum = prefixSum[i + 1] - prefixSum[mid];
                const need = (i - mid + 1) * nums[i] - curSum;
                if (need <= k) {
                    right = mid - 1;
                    res = Math.max(res, i - mid + 1);
                } else {
                    left = mid + 1;
                }
            }
        }
        return res;
    }
}

public class Solution {
    public int MaxFrequency(int[] nums, int k) {
        Array.Sort(nums);
        int n = nums.Length;
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        int res = 1;
        for (int i = 0; i < n; i++) {
            int left = 0, right = i;
            while (left <= right) {
                int mid = (left + right) / 2;
                long curSum = prefixSum[i + 1] - prefixSum[mid];
                long need = (long)(i - mid + 1) * nums[i] - curSum;
                if (need <= k) {
                    res = Math.Max(res, i - mid + 1);
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return res;
    }
}

func maxFrequency(nums []int, k int) int {
    sort.Ints(nums)
    n := len(nums)
    prefixSum := make([]int64, n+1)
    for i := 0; i < n; i++ {
        prefixSum[i+1] = prefixSum[i] + int64(nums[i])
    }

    res := 1
    for i := 0; i < n; i++ {
        left, right := 0, i
        for left <= right {
            mid := (left + right) / 2
            curSum := prefixSum[i+1] - prefixSum[mid]
            need := int64(i-mid+1)*int64(nums[i]) - curSum
            if need <= int64(k) {
                right = mid - 1
                if i-mid+1 > res {
                    res = i - mid + 1
                }
            } else {
                left = mid + 1
            }
        }
    }
    return res
}

class Solution {
    fun maxFrequency(nums: IntArray, k: Int): Int {
        nums.sort()
        val n = nums.size
        val prefixSum = LongArray(n + 1)
        for (i in 0 until n) {
            prefixSum[i + 1] = prefixSum[i] + nums[i]
        }

        var res = 1
        for (i in 0 until n) {
            var left = 0
            var right = i
            while (left <= right) {
                val mid = (left + right) / 2
                val curSum = prefixSum[i + 1] - prefixSum[mid]
                val need = (i - mid + 1).toLong() * nums[i] - curSum
                if (need <= k) {
                    right = mid - 1
                    res = maxOf(res, i - mid + 1)
                } else {
                    left = mid + 1
                }
            }
        }
        return res
    }
}

class Solution {
    func maxFrequency(_ nums: [Int], _ k: Int) -> Int {
        let nums = nums.sorted()
        let n = nums.count
        var prefixSum = [Int](repeating: 0, count: n + 1)
        for i in 0..<n {
            prefixSum[i + 1] = prefixSum[i] + nums[i]
        }

        var res = 1
        for i in 0..<n {
            var left = 0, right = i
            while left <= right {
                let mid = (left + right) / 2
                let curSum = prefixSum[i + 1] - prefixSum[mid]
                let need = (i - mid + 1) * nums[i] - curSum
                if need <= k {
                    right = mid - 1
                    res = max(res, i - mid + 1)
                } else {
                    left = mid + 1
                }
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Sliding Window

Intuition

Since the array is sorted, we can use a sliding window. As we expand the window by moving the right pointer, we add elements and check if the cost to make all elements equal to the rightmost exceeds k. If it does, we shrink from the left.

The cost for a window is target * window_size - window_sum. When this exceeds k, we need a smaller window. The window always represents a valid subarray that can be made uniform within budget.

Algorithm

Sort the array.
Initialize l = 0, total = 0, and res = 0.
For each right index r:
- Add nums[r] to total.
- While nums[r] * (r - l + 1) > total + k:
  - Subtract nums[l] from total and increment l.
- Update res with r - l + 1.
Return res.

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        total = res = 0
        l = 0

        for r in range(len(nums)):
            total += nums[r]
            while nums[r] * (r - l + 1) > total + k:
                total -= nums[l]
                l += 1
            res = max(res, r - l + 1)

        return res

public class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        long total = 0;
        int res = 0;
        int l = 0;

        for (int r = 0; r < nums.length; r++) {
            total += nums[r];
            while ((long) nums[r] * (r - l + 1) > total + k) {
                total -= nums[l];
                l++;
            }
            res = Math.max(res, r - l + 1);
        }

        return res;
    }
}

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long long total = 0;
        int res = 0, l = 0;

        for (int r = 0; r < nums.size(); ++r) {
            total += nums[r];
            while ((long long)nums[r] * (r - l + 1) > total + k) {
                total -= nums[l];
                l++;
            }
            res = max(res, r - l + 1);
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    maxFrequency(nums, k) {
        nums.sort((a, b) => a - b);
        let total = 0,
            res = 0,
            l = 0;

        for (let r = 0; r < nums.length; r++) {
            total += nums[r];
            while (nums[r] * (r - l + 1) > total + k) {
                total -= nums[l];
                l++;
            }
            res = Math.max(res, r - l + 1);
        }

        return res;
    }
}

public class Solution {
    public int MaxFrequency(int[] nums, int k) {
        Array.Sort(nums);
        long total = 0;
        int res = 0, l = 0;

        for (int r = 0; r < nums.Length; r++) {
            total += nums[r];
            while ((long)nums[r] * (r - l + 1) > total + k) {
                total -= nums[l];
                l++;
            }
            res = Math.Max(res, r - l + 1);
        }

        return res;
    }
}

func maxFrequency(nums []int, k int) int {
    sort.Ints(nums)
    var total int64 = 0
    res, l := 0, 0

    for r := 0; r < len(nums); r++ {
        total += int64(nums[r])
        for int64(nums[r])*int64(r-l+1) > total+int64(k) {
            total -= int64(nums[l])
            l++
        }
        if r-l+1 > res {
            res = r - l + 1
        }
    }

    return res
}

class Solution {
    fun maxFrequency(nums: IntArray, k: Int): Int {
        nums.sort()
        var total = 0L
        var res = 0
        var l = 0

        for (r in nums.indices) {
            total += nums[r]
            while (nums[r].toLong() * (r - l + 1) > total + k) {
                total -= nums[l]
                l++
            }
            res = maxOf(res, r - l + 1)
        }

        return res
    }
}

class Solution {
    func maxFrequency(_ nums: [Int], _ k: Int) -> Int {
        let nums = nums.sorted()
        var total = 0
        var res = 0
        var l = 0

        for r in 0..<nums.count {
            total += nums[r]
            while nums[r] * (r - l + 1) > total + k {
                total -= nums[l]
                l += 1
            }
            res = max(res, r - l + 1)
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

4. Advanced Sliding Window

Intuition

We can optimize further by observing that we only care about the maximum window size. Once we find a valid window of size w, we never need a smaller window. So instead of shrinking until valid, we can just slide the window forward, maintaining its size when invalid.

If a new element causes the window to become invalid, we remove exactly one element from the left, keeping the window size the same. The window size only grows when we find a valid configuration.

Algorithm

Sort the array.
Initialize l = 0 and total = 0.
For each right index r:
- Add nums[r] to total.
- If (r - l + 1) * nums[r] > total + k:
  - Subtract nums[l] from total and increment l.
The final window size is n - l which equals the maximum frequency.
Return this value.

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        l = 0
        total = 0

        for r in range(len(nums)):
            total += nums[r]

            if (r - l + 1) * nums[r] > total + k:
                total -= nums[l]
                l += 1

        return len(nums) - l

public class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        long total = 0;
        int l = 0;

        for (int r = 0; r < nums.length; r++) {
            total += nums[r];
            if ((r - l + 1) * 1L * nums[r] > total + k) {
                total -= nums[l];
                l++;
            }
        }

        return nums.length - l;
    }
}

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long long total = 0;
        int l = 0;

        for (int r = 0; r < nums.size(); ++r) {
            total += nums[r];
            if ((r - l + 1) * 1L * nums[r] > total + k) {
                total -= nums[l];
                l++;
            }
        }

        return nums.size() - l;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    maxFrequency(nums, k) {
        nums.sort((a, b) => a - b);
        let total = 0,
            l = 0;

        for (let r = 0; r < nums.length; r++) {
            total += nums[r];
            if (nums[r] * (r - l + 1) > total + k) {
                total -= nums[l];
                l++;
            }
        }

        return nums.length - l;
    }
}

public class Solution {
    public int MaxFrequency(int[] nums, int k) {
        Array.Sort(nums);
        long total = 0;
        int l = 0;

        for (int r = 0; r < nums.Length; r++) {
            total += nums[r];
            if ((long)(r - l + 1) * nums[r] > total + k) {
                total -= nums[l];
                l++;
            }
        }

        return nums.Length - l;
    }
}

func maxFrequency(nums []int, k int) int {
    sort.Ints(nums)
    var total int64 = 0
    l := 0

    for r := 0; r < len(nums); r++ {
        total += int64(nums[r])
        if int64(r-l+1)*int64(nums[r]) > total+int64(k) {
            total -= int64(nums[l])
            l++
        }
    }

    return len(nums) - l
}

class Solution {
    fun maxFrequency(nums: IntArray, k: Int): Int {
        nums.sort()
        var total = 0L
        var l = 0

        for (r in nums.indices) {
            total += nums[r]
            if ((r - l + 1).toLong() * nums[r] > total + k) {
                total -= nums[l]
                l++
            }
        }

        return nums.size - l
    }
}

class Solution {
    func maxFrequency(_ nums: [Int], _ k: Int) -> Int {
        let nums = nums.sorted()
        var total = 0
        var l = 0

        for r in 0..<nums.count {
            total += nums[r]
            if (r - l + 1) * nums[r] > total + k {
                total -= nums[l]
                l += 1
            }
        }

        return nums.count - l
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

Common Pitfalls

Forgetting to Sort the Array

The sliding window and binary search approaches only work on a sorted array. Without sorting, elements that could be incremented to match a target value are scattered throughout the array, making it impossible to find contiguous windows efficiently. Always sort first before applying the window techniques.

Integer Overflow in Cost Calculation

When calculating the cost (window_size) * target - window_sum, the multiplication can overflow if using 32-bit integers. For large arrays with values up to 10^5, the product can exceed 2^31. Use long or long long for the total variable and cast appropriately before multiplication.

Incorrect Window Shrinking Condition

A common mistake is using >= instead of > when checking if the window is invalid. The condition should be nums[r] * (r - l + 1) > total + k (strictly greater), not >=. Using >= would shrink valid windows prematurely, potentially missing the optimal answer.