Frequency of the Most Frequent Element - Solution & Explanation
Problem Statement
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 <= 1051 <= nums[i] <= 1051 <= k <= 105
Approach Overview
Problem Overview: You are given an integer array and an integer k. In one operation you can increment any element by 1. The goal is to maximize the frequency of some value after performing at most k increments. In other words, determine the largest group of equal numbers you can create by increasing smaller numbers.
Approach 1: Sliding Window Technique (O(n log n) time, O(1) space)
The key observation: if the array is sorted, you only need to raise smaller numbers to match a larger number on the right. After sorting, maintain a sliding window where the right pointer represents the target value all elements should match. Track the running sum of the window. The cost to convert all numbers in the window to nums[right] is nums[right] * window_size - window_sum. If that cost exceeds k, move the left pointer to shrink the window until the cost becomes valid again.
This works because sorting guarantees that increasing elements only moves them toward the current maximum. Each element enters and leaves the window once, so the window scan is linear. The only expensive step is sorting. This approach combines sorting with a classic sliding window pattern to efficiently track the largest feasible group.
Approach 2: Binary Search with Prefix Sums (O(n log n) time, O(n) space)
Another strategy treats the answer (maximum frequency) as a search space. After sorting the array, precompute a prefix sum array so you can quickly calculate the sum of any subarray. Then binary search on the possible frequency f. For each candidate frequency, check whether there exists a window of size f that can be converted to the same value using at most k increments.
To verify a window ending at index i, compute the cost to raise all elements in that window to nums[i]. Using prefix sums, the subarray sum is retrieved in O(1). The required operations become nums[i] * f - window_sum. If any window satisfies the k constraint, that frequency is feasible.
This approach explicitly searches the answer space using binary search. It is slightly more verbose than the sliding window solution but useful when you want a structured way to reason about feasibility problems.
Recommended for interviews: The sliding window approach is the expected solution. It shows you recognize that sorting converts the problem into expanding and shrinking a window based on operation cost. Binary search with prefix sums is also correct but usually considered a secondary method. Demonstrating the sliding window insight signals strong pattern recognition and optimization skills.
Approach 1: Approach 1: Sliding Window Technique
The sliding window technique is used to find the longest subarray where elements can be incremented to make them equal using at most k increments. We sort the array first to ensure it's easier to increment elements to become equal. We then use two pointers: one for the current end of the subarray and the other to represent the start. By checking the cost to transform the current subarray into an equal value using the difference between values and leveraging the sorted property, we can determine the maximum frequency we can achieve.
The C solution utilizes quick sort to sort the array and then employs two pointers, along with cumulative sums, to check the feasibility of increasing all numbers between two points to the right pointer's number with at most k increments. The result is updated to reflect the maximum length of this window that satisfies the condition.
Complexity
Time Complexity: O(n log n), due to sorting the array.
Space Complexity: O(1), as no extra space is used apart from variable allocations.
Approach 2: Approach 2: Binary Search with Prefix Sums
This approach makes use of binary search in combination with prefix sums to efficiently find the maximum frequency possible by transforming elements. We first sort the array. For a given target frequency, we check through calculating the required increment operations using a prefix sum array and binary searching over possible solutions. This allows us to leverage efficient range queries and reduce time complexity.
In this solution, a prefix sum array is built first, followed by using binary search to find the maximum frequency feasible. By leveraging prefix sums, we efficiently verify if a frequency can be achieved via permissible operations within k increments across the array (checking subarrays of certain length).
Complexity
Time Complexity: O(n log n), because of sorting and binary search iterations.
Space Complexity: O(n), due to additional space for prefix sums.
Approach 3: Sorting + Prefix Sum + Binary Search
According to the problem description, we can draw three conclusions:
- After several operations, the element with the highest frequency in the array must be an element in the original array. Why? Suppose the elements operated are
a_1, a_2, cdots, a_m, where the maximum isa_m. These elements have all been changed to the same valuex, wherex geq a_m. Then we can also change these elements all toa_m, and the number of operations will not increase. - The elements operated must be a continuous subarray in the sorted array.
- If a frequency
msatisfies the condition, then allm' < malso satisfy the condition. This inspires us to consider using binary search to find the maximum frequency that satisfies the condition.
Therefore, we can sort the array nums and then calculate the prefix sum array s of the sorted array, where s[i] represents the sum of the first i elements.
Next, we define the left boundary of the binary search as l = 1, and the right boundary as r = n. For each binary search, we take the middle value m = (l + r + 1) / 2, and then check whether there exists a continuous subarray of length m such that all elements in the subarray can be changed to an element in the array, and the number of operations does not exceed k. If such a subarray exists, we can update the left boundary l to m, otherwise update the right boundary r to m - 1.
Finally, return the left boundary l.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Sorting + Two Pointers
We can also use two pointers to maintain a sliding window, where all elements in the window can be changed to the maximum value in the window. The number of operations for the elements in the window is s, and s leq k.
Initially, we set the left pointer j to point to the first element of the array, and the right pointer i also points to the first element of the array. Next, we move the right pointer i each time, changing all elements in the window to nums[i]. At this time, the number of operations to be increased is (nums[i] - nums[i - 1]) times (i - j). If this number of operations exceeds k, then we need to move the left pointer j until the number of operations for the elements in the window does not exceed k. Then, we update the answer to the maximum length of the window.
The time complexity is O(n log n), and the space complexity is O(log n). Where n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sliding Window Technique | Time Complexity: O(n log n), due to sorting the array. Space Complexity: O(1), as no extra space is used apart from variable allocations. |
| Approach 2: Binary Search with Prefix Sums | Time Complexity: O(n log n), because of sorting and binary search iterations. Space Complexity: O(n), due to additional space for prefix sums. |
| Sorting + Prefix Sum + Binary Search | — |
| Sorting + Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Sorting | O(n log n) | O(1) | Best general solution; efficient after sorting and commonly expected in interviews |
| Binary Search with Prefix Sums | O(n log n) | O(n) | Useful when treating frequency as a search space and validating ranges quickly |
Video Solution
Frequency of the Most Frequent Element - Sliding Window - Leetcode 1838 • NeetCode • 129,669 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Frequency of the Most Frequent Element easy or hard?
Frequency of the Most Frequent Element Python/Java solution
How to solve Frequency of the Most Frequent Element in O(n)?
What is the best approach for Frequency of the Most Frequent Element?
Is Frequency of the Most Frequent Element asked at Google/Amazon/Meta?
What data structure is used in Frequency of the Most Frequent Element?
What is the time complexity of Frequency of the Most Frequent Element?
Ready to solve this problem?
Practice Frequency of the Most Frequent Element with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor