Sliding Window - Frequency of the Most Frequent Element

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.

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.

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.

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

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= 10⁵

Solution 1 - Sort input array, then apply sliding window technique

In this approach, we are going to sort the input array first, then apply sliding window technique. The reason we will sort the array is because, the right most element of the window should be either equal or greater than the left side elements, so that we know the value to what we will make its left side elements to. For example, after sorting the input array is [1, 2, 5, 9, 11], say we are at window left =0, right =2, since we know right element is '5', we need to make left side elements in the same window to 5 as well to make that most frequent element in that window.

Implementation steps:

First, we will sort the input array nums.
Then, create four variables left, right that we will use to adjust the window, sum to hold cumulative sum of elements in the current window, and maxFrequency to hold the maximum frequency result.
Next, run a while loop until right pointer reaches end of array nums, and do the following:
- Add current element value to sum.
- Then, check if the current window is going out of bounds, that is if we make all of the elements in the current window to match same as right element of the window. (right - left + 1) * nums[right] > sum + k What we are doing here is, to match all left side elements in current window to same as current element (right indexed element), we need a value that should be either less than or equal to window length * curent element, so we are checking it against sum + k (cumulative sum of elements in current window and k values we can distribute among the elements in current window). So if the window length * curent element is greater than sum + k that means we are going out bounds and move the sliding window. So, to move the next window, run a while loop until the above condition is true, and subtract left pointer element value from sum and increment left pointer.
  For example, say if the array is [1, 2, 4, 9], and k =2, when we are at window left =0, right =2 sum = 1 + 2 + 4 = 7 . In order to make all of the current elements to 4, the total will be 12, but current sum is 7 and k=2, if we sum these sum + k = 7 + 2 = 9, so with k =2, we cannot make all current window elements to 4, so we have to move the slinding window to next position.
- Next, update the maxFrequecy with maximum value between current window size and the current maxFrequency.
- At the end of while loop increment right pointer to move to the next character.
Finally, return maxFrequency.

import java.util.Arrays; public class FrequencyOfTheMostFrequentElement { static int maxFrequency(int[] nums, int k) { Arrays.sort(nums); // O(n log n) int left = 0; int right=0; int maxFrequency = 0; long sum = 0; while(right < nums.length) { sum += nums[right]; /* window length * nums[right] --> this is the value if we make all of left side elements same as current element. sum +k --> cumulative sum, and we can distribute K among those numbers. if left side value is greater, then we won't be able to all of left side elements in current window to same as current element. So, we will shift the window. */ while((long) (right - left + 1) * nums[right] > sum+k) { sum -= nums[left]; left++; } maxFrequency = Math.max(maxFrequency, right-left+1); right++; } return maxFrequency; } public static void main(String[] args) { System.out.println(maxFrequency(new int[]{1,1,1,2,2,4}, 3)); System.out.println(maxFrequency(new int[]{1,4,8,13}, 5)); System.out.println(maxFrequency(new int[]{1,2,4}, 5)); System.out.println(maxFrequency(new int[]{3,9,6}, 2)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n log(n)) time, where n is the length of input array nums, because we are sorting the array.
Space complexity: O(1), assumming that sorting will be done in-place algorithms like QuickSort

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: