1838. Frequency of the Most Frequent Element
Problem Description
You are given an integer array nums
and an integer k
. The task is to find the maximum frequency of any element in nums
after you're allowed to increment any element by 1 up to k
times. The frequency of an element is how many times that element appears in the array. The objective is to find the highest possible frequency of any number in the array after making at most k
increments in total.
Intuition
The intuition behind the solution is to first sort the array. By doing this, we can then use a sliding window to check each subarray and calculate how many operations we would need to make all elements in the subarray equal to the rightmost element.
Starting with the smallest elements on the left, we work towards the right. For each position r
(right end of the window), we calculate the number of operations needed to raise all elements from l
(left end of the window) to r
to the value of the element at position r
. This is done by multiplying the difference between nums[r]
and nums[r - 1]
by r - l
(size of the current window minus one).
If the total operations required exceed k
, we shrink the window from the left by increasing l
, subtracting the necessary operations as we go to keep the window valid (total operations less than or equal to k
). Meanwhile, we're always keeping track of the maximum window size we're able to achieve without exceeding k
operations, as this directly corresponds to the maximum frequency.
The solution uses a two-pointer technique to maintain the window, expanding and shrinking it as needed while traversing the sorted array only once, which gives an efficient time complexity.
Learn more about Greedy, Binary Search, Prefix Sum, Sorting and Sliding Window patterns.
Solution Approach
The algorithm implemented in the given solution follows a sliding window approach using two pointers, l
and r
, which represent the left and right ends of the window, respectively. The fundamental data structure used here is the list (nums
), which is sorted to facilitate the sliding window logic. Here is a step-by-step breakdown:
-
Sort the Array: The array
nums
is sorted to allow comparing adjacent elements and to use the sliding window technique effectively.1nums.sort()
-
Initialize Pointers and Variables: Three variables are initialized:
l
(left pointer) which starts at 0.r
(right pointer) which starts at 1 since the window should at least contain one element to make comparisons.ans
which keeps track of the maximum frequency found.window
which holds the total number of operations performed in the current window.
1l, r, window = 0, 1, 0 2ans = 1 # A single element has at least a frequency of 1.
-
Expand the Window: The algorithm enters a loop that continues until the right pointer
r
reaches the end of the array.1while r < len(nums):
-
Calculate Operations: In each iteration, calculate the operations needed to increment all numbers in the current window to the value of
nums[r]
.1window += (nums[r] - nums[r - 1]) * (r - l)
-
Shrink the Window: If
window
exceedsk
, meaning we cannot increment the elements of the current window to matchnums[r]
with the allowed number of operations, movel
to the right to reduce the size of the window untilwindow
is within the limit again.1while window > k: 2 window -= nums[r] - nums[l] 3 l += 1
-
Update Maximum Frequency: After adjusting the window to ensure we do not exceed
k
operations, update the maximum frequencyans
if the current window size (r - l
) is greater than the previous maximum.1r += 1 2ans = max(ans, r - l)
-
Return the Result: Once we have finished iterating through the array with the right pointer
r
, theans
variable holds the maximum frequency that can be achieved, and we return it.1return ans
The sliding window technique coupled with the sorted nature of the array allows for an efficient solution. This technique avoids recalculating the increment operations for each window from scratch; instead, it updates the number of operations incrementally as the window expands or shrinks.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach in action:
Suppose we have an array nums = [1, 2, 3]
and k = 3
.
-
First, we sort
nums
, which in this case is already sorted:[1, 2, 3]
. -
Initialize the pointers and variables:
l = 0
,r = 1
,window = 0
, andans = 1
. -
Enter the loop.
nums[r]
is2
, andnums[l]
is1
.window
becomes(2 - 1) * (1 - 0) = 1
. -
Since
window <= k
, we do not need to shrink the window. We then updateans
with the new window size, which isr - l
.ans = max(1, 1 - 0) = 1
. -
Increment
r
and it becomes2
. -
Next iteration,
nums[2]
is3
. We calculate operations needed:window += (3 - 2) * (2 - 0) = 1 + 2 = 3
. -
Again,
window <= k
, so we do not shrink the window. Updateans = max(1, 2 - 0) = 2
. -
Increment
r
and it becomes3
. Sincer
is now equal tolen(nums)
, the loop ends. -
Return
ans
. So the maximum frequency afterk
increments is2
.
Putting it all together, we found that after incrementing the elements optimally, we can have at least two elements with the same value in the array [1, 2, 3]
by using at most 3
increments (for example: incrementing 1
and 2
to make the array [3, 3, 3]
). Thus, the maximum frequency is 2
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maxFrequency(self, nums: List[int], k: int) -> int:
5 # Sort the input list in non-decreasing order.
6 nums.sort()
7
8 # Initialize two pointers for sliding window and the variables needed.
9 left, right, n = 0, 1, len(nums)
10 max_freq, cumulative_diff = 1, 0
11
12 # Iterate with right pointer over the list to expand the window.
13 while right < n:
14 # Increase the total difference by the difference between the current right element
15 # and its predecessor multiplied by the number of elements in the current window.
16 cumulative_diff += (nums[right] - nums[right - 1]) * (right - left)
17
18 # If the cumulative differences exceed k, shrink the window from the left.
19 while cumulative_diff > k:
20 cumulative_diff -= nums[right] - nums[left]
21 left += 1
22
23 # Move the right pointer to the next element in the list.
24 right += 1
25
26 # Update the maximum frequency using the current window size.
27 max_freq = max(max_freq, right - left)
28
29 # Return the maximum frequency achievable with total operations <= k.
30 return max_freq
31
32# The class and method could be tested with a simple test case as follows:
33# sol = Solution()
34# print(sol.maxFrequency([1,2,4], 5)) # Expected output: 3
35
1class Solution {
2 // Function to find the maximum frequency of an element after performing operations
3 public int maxFrequency(int[] nums, int k) {
4 // Sort the array to group similar elements together
5 Arrays.sort(nums);
6
7 int n = nums.length; // Store the length of the array for iteration
8 int maxFreq = 1; // Initialize max frequency as 1 (at least one number is always there)
9 int operationsSum = 0; // This will hold the sum of operations used at any point
10
11 // Start with two pointers:
12 // 'left' at 0 for the start of the window,
13 // 'right' at 1, since we'll start calculating from the second element
14 for (int left = 0, right = 1; right < n; ++right) {
15 // Calculate the total operations done to make all elements from 'left' to 'right' equal to nums[right]
16 operationsSum += (nums[right] - nums[right - 1]) * (right - left);
17
18 // If the total operations exceed k, shrink the window from the left
19 while (operationsSum > k) {
20 operationsSum -= (nums[right] - nums[left++]);
21 }
22
23 // Calculate the max frequency based on the window size and update it if necessary
24 maxFreq = Math.max(maxFreq, right - left + 1);
25 }
26
27 // Return the maximum frequency
28 return maxFreq;
29 }
30}
31
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 int maxFrequency(std::vector<int>& nums, int k) {
7 // Sort the given vector.
8 std::sort(nums.begin(), nums.end());
9
10 // Initialize variables: n is the size of the vector,
11 // ans will hold the maximum frequency.
12 int n = nums.size();
13 int maxFrequency = 1;
14
15 // 'window' represents the total increments needed to make
16 // all elements in the current window equal to the current maximum element.
17 long long window = 0;
18
19 // Using two pointers technique: l -> left, r -> right.
20 // Beginning with the second element as there's nothing to the left of the first.
21 for (int left = 0, right = 1; right < n; ++right) {
22 // Update the 'window' with the cost of bringing the newly included
23 // element nums[right] to the value of nums[right - 1].
24 window += 1LL * (nums[right] - nums[right - 1]) * (right - left);
25
26 // If the total increments exceed k, shrink the window from the left.
27 while (window > k) {
28 window -= (nums[right] - nums[left]);
29 left++;
30 }
31
32 // Calculate max frequency by finding the maximum window size till now.
33 maxFrequency = std::max(maxFrequency, right - left + 1);
34 }
35
36 // Return the maximum frequency found.
37 return maxFrequency;
38 }
39};
40
1function maxFrequency(nums: number[], k: number): number {
2 // Sort the array
3 nums.sort((a, b) => a - b);
4
5 // Initialize the answer with a single element frequency
6 let maxFrequency = 1;
7
8 // Initialize a variable to keep track of the total sum that needs to be added to make all elements equal during a window slide
9 let windowSum = 0;
10
11 // Get the count of elements in the array
12 let n = nums.length;
13
14 // Initialize two pointers for our sliding window technique
15 for (let left = 0, right = 1; right < n; right++) {
16 // Update the window sum by adding the cost of making the right-most element equal to the current right-most element
17 windowSum += (nums[right] - nums[right - 1]) * (right - left);
18
19 // Shrink the window from the left if the cost exceeds the value of k
20 while (windowSum > k) {
21 windowSum -= nums[right] - nums[left];
22 left++;
23 }
24
25 // Update the maximum frequency with the current window size if it's greater
26 maxFrequency = Math.max(maxFrequency, right - left + 1);
27 }
28
29 // Return the maximum frequency achieved
30 return maxFrequency;
31}
32
Time and Space Complexity
Time Complexity
The provided code first sorts the nums
list, and then uses a two-pointer approach to iterate over the list, adjusting the window of elements that can be made equal by applying up to k
operations.
- Sorting the list: Sorting takes
O(n log n)
time, wheren
is the number of elements innums
. - Two-pointer window iteration: The while loop iterates over the sorted list, adjusting the window of elements by incrementing the right pointer and potentially the left pointer. The right pointer makes only one pass over the list, resulting in
O(n)
operations. The left pointer moves only in one direction and can move at mostn
times, so it also contributes toO(n)
operations.
Combining the sort and the two-pointer iteration results in a time complexity of O(n log n + n)
, which simplifies to O(n log n)
since n log n
dominates n
for large n
.
Therefore, the overall time complexity of the code is O(n log n)
.
Space Complexity
The space complexity of the code depends on the space used to sort the list and the additional variables used for the algorithm.
- Sorting the list: The sort operation on the list is in-place; however, depending on the sorting algorithm implemented in Python (Timsort), the sorting can take up to
O(n)
space in the worst case. - Additional variables: The code uses a few additional variables (
l
,r
,n
,ans
,window
). These require constant space (O(1)
).
Therefore, considering both the sorting and the additional variables, the space complexity of the code is O(n)
in the worst case due to the sorting operation's space requirement.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.