1838

1838. Frequency of the Most Frequent Element (Medium)

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.

Example 3:

Input: nums = [3,9,6], k = 2
Output: 1

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• 1 <= k <= 105

Companies: Amazon, Deutsche Bank, Uber, CRED, Microsoft, PhonePe, Apple, Google, Pony.ai

Related Topics:
Array, Binary Search, Greedy, Sliding Window, Sorting, Prefix Sum

Similar Questions:

• Find All Lonely Numbers in the Array (Medium)
• Longest Nice Subarray (Medium)

Hints:

• Note that you can try all values in a brute force manner and find the maximum frequency of that value.
• To find the maximum frequency of a value consider the biggest elements smaller than or equal to this value

Solution 1. Sliding window (Shrinkable)

Check out "C++ Maximum Sliding Window Cheatsheet Template!"

Since we only care about the frequency, we can sort the array first to simplify the problem.

Let two pointers i, j form a window [i, j]. The window is valid if (j - i + 1) * A[j] - sum <= k where sum is the sum of the numbers in window [i, j].

We increment j and update sum, then shrink the window by incrementing i until the window become valid again.

Then the window [i, j] with length j - i + 1 is the maximum window we've seen so far.

// OJ: https://leetcode.com/problems/frequency-of-the-most-frequent-element/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int maxFrequency(vector<int>& A, int k) {
        sort(begin(A), end(A));
        long i = 0, N = A.size(), ans = 1, sum = 0;
        for (int j = 0; j < N; ++j) {
            sum += A[j];
            while ((j - i + 1) * A[j] - sum > k) sum -= A[i++];
            ans = max(ans, j - i + 1);
        }
        return ans;
    }
};

Solution 2. Sliding window (Non-shrinkable)

// OJ: https://leetcode.com/problems/frequency-of-the-most-frequent-element/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int maxFrequency(vector<int>& A, int k) {
        sort(begin(A), end(A));
        long i = 0, j = 0, N = A.size(), sum = 0;
        for (; j < N; ++j) {
            sum += A[j];
            if ((j - i + 1) * A[j] - sum > k) sum -= A[i++];
        }
        return j - i;
    }
};

Discuss

https://leetcode.com/problems/frequency-of-the-most-frequent-element/discuss/1175088/C%2B%2B-Maximum-Sliding-Window-Cheatsheet-Template!