Problem

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.

Examples

Example 1:

1
2
3
4

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:

1
2
3
4
5
6

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:

1
2

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

Solution

Method 1 - Sorting + Sliding Window Technique

In e.g.1, we were lucky, that array was sorted. So, we can easily see where we are allocating our budget k to elements in array to make them most frequent. Finding difference between 2 elements is easier to find in sorted array.

  1. First sort the array nums.
  2. In order to calculate the maximum frequency of a number, we can increment some numbers less than it. Let this number be x.
  3. Let l is left pointer and r is right pointer. Window size size = (r-l+1)
  4. We assume number we are finding is on right pointer, and we allocate budget k to numbers smaller than it. When all numbers in window become x, total sum here should be x*size. Suppose, all the numbers which are part of solution add up to sum. Then this condition holds: k + sum >= size * x k+sum[r:l] >= (r-l+1) * nums[r] nums[r] * (r-l+1) - sums[r:l] <=k Because if it is less, we are out of k, our budget.
  5. Our answer is window size.

Also, remember to use long for sums, to avoid overflow.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public int maxFrequency(int[] nums, int k) {
	int n = nums.length;
	
	Arrays.sort(nums);
	
	int ans = 0;
	int l = 0;
	
	long sum = 0;
	
	for(int r=0; r < n; r++) {
		sum += nums[r];
		
		// shrink window from left
		while(nums[r]*(r-l+1)-sum>k) {
			sum -= nums[l];
			l++;
		}
		
		ans = Math.max(ans, r-l+1);
	}
	
	return ans;
}

Complexity

Now problem becomes O(n log n) + O(n) = O(n log n)