2023-11-18 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 18

Description

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.

 

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 <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= 105

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  using ll = long long;
public:
  int maxFrequency(vector<int>& nums, int k) {
    if(nums.size() == 1) return 1;
    sort(nums.begin(), nums.end());
    int begin = 0;
    int answer = 0;
    ll currentSum = nums[0];
    ll beginSum = 0;
    for(int end = 1; end < nums.size(); ++end) {
      currentSum += nums[end];
      while(begin < end && 1LL * nums[end] * (end + 1 - begin) - (currentSum - beginSum) > k) {
        beginSum += nums[begin];
        begin += 1;
      }
      answer = max(answer, end - begin + 1);
    }
    return answer;
  }
};

// Accepted
// 71/71 cases passed (128 ms)
// Your runtime beats 97.54 % of cpp submissions
// Your memory usage beats 25.45 % of cpp submissions (99.5 MB)
Algorithm