Leetcode 1838. Frequency of the Most Frequent Element Solution
Problem Explanation
You are given an integer array nums
and an integer k
. The goal is to perform at most 'k' operations on the array, where each operation consists of incrementing an element by 1, and find the maximum possible frequency of an element after performing these operations.
Solution Approach
To solve this problem, we will use the sliding window approach:
- Sort the input array
nums
. - Initialize two pointers,
l
andr
, and a variablesum
to keep track of the sum of elements in the window. - Iterate through the array using the
r
pointer, and for each element, add its value tosum
. - If the sum + k is less than the element at position
r
times the window size (r - l + 1), we remove the element at positionl
from the sum and increment thel
pointer. This condition checks if the window's sum + k is large enough to perform 'k' operations to make all elements in the window equal to the current element at positionr
. - Calculate the maximum frequency by taking the maximum between the current maximum and the window size (r - l + 1).
Let's walk through an example:
1nums = [1, 4, 8, 13], k = 5
- Sort the array:
nums = [1, 4, 8, 13]
. The array is already sorted in this case. - Initialize
l = 0
,r = 0
, andsum = 0
. - Start iterating through the array.
- For
r = 0
, sum += nums[0] = 1. - For
r = 1
, sum += nums[1] = 5. Withsum + k = 10
, the condition in step 4 does not apply, so the maximum frequency is updated tor - l + 1 = 2
. - For
r = 2
, sum += nums[2] = 13.sum + k = 18
, which is less thannums[2] * (r - l + 1)
or24
. So, we removenums[l]
from the sum and incrementl
. Now,sum = 12
, and the maximum frequency remains 2. - For
r = 3
, sum += nums[3] = 25.sum + k = 30
, which is less thannums[3] * (r - l + 1)
or52
. So, we removenums[l]
from the sum and incrementl
. Now,sum = 21
,l = 2
, and the maximum frequency remains 2.
- For
- The iteration is complete, and the maximum frequency is 2.
Python Solution
1class Solution:
2 def maxFrequency(self, nums: List[int], k: int) -> int:
3 ans = 0
4 sum = 0
5
6 nums.sort()
7
8 l = 0
9 for r in range(len(nums)):
10 sum += nums[r]
11 while sum + k < nums[r] * (r - l + 1):
12 sum -= nums[l]
13 l += 1
14 ans = max(ans, r - l + 1)
15
16 return ans
Java Solution
1class Solution {
2 public int maxFrequency(int[] nums, int k) {
3 int ans = 0;
4 long sum = 0;
5
6 Arrays.sort(nums);
7
8 int l = 0;
9 for (int r = 0; r < nums.length; r++) {
10 sum += nums[r];
11 while (sum + k < (long)nums[r] * (r - l + 1)) {
12 sum -= nums[l++];
13 }
14 ans = Math.max(ans, r - l + 1);
15 }
16
17 return ans;
18 }
19}
JavaScript Solution
1class Solution {
2 maxFrequency(nums, k) {
3 let ans = 0;
4 let sum = 0;
5
6 nums.sort((a, b) => a - b);
7
8 let l = 0;
9 for (let r = 0; r < nums.length; r++) {
10 sum += nums[r];
11 while (sum + k < nums[r] * (r - l + 1)) {
12 sum -= nums[l++];
13 }
14 ans = Math.max(ans, r - l + 1);
15 }
16
17 return ans;
18 }
19}
C++ Solution
1class Solution {
2 public:
3 int maxFrequency(vector<int>& nums, int k) {
4 int ans = 0;
5 long sum = 0;
6
7 sort(nums.begin(), nums.end());
8
9 int l = 0;
10 for (int r = 0; r < nums.size(); r++) {
11 sum += nums[r];
12 while (sum + k < static_cast<long>(nums[r]) * (r - l + 1)) {
13 sum -= nums[l++];
14 }
15 ans = max(ans, r - l + 1);
16 }
17
18 return ans;
19 }
20};
C# Solution
1public class Solution {
2 public int MaxFrequency(int[] nums, int k) {
3 int ans = 0;
4 long sum = 0;
5
6 Array.Sort(nums);
7
8 int l = 0;
9 for (int r = 0; r < nums.Length; r++) {
10 sum += nums[r];
11 while (sum + k < (long)nums[r] * (r - l + 1)) {
12 sum -= nums[l++];
13 }
14 ans = Math.Max(ans, r - l + 1);
15 }
16
17 return ans;
18 }
19}
In conclusion, we have provided the optimal solution for the problem using the sliding window approach. The solution has been implemented in Python, Java, JavaScript, C++, and C#. The time complexity of the solution is O(N * log(N)), where N is the number of elements in the input array, due to the sorting of the array. The space complexity is O(1), as no additional data structures are required.