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 <= 105The 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.
C++
Java
Python
C#
JavaScript
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.
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).
C++
Java
Python
C#
JavaScript
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 | 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. |
Top K Frequent Elements - Bucket Sort - Leetcode 347 - Python • NeetCode • 665,789 views views
Watch 9 more video solutions →Practice Frequency of the Most Frequent Element with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor