3346. Maximum Frequency of an Element After Performing Operations I LeetCode Solution

In this guide, you will get 3346. Maximum Frequency of an Element After Performing Operations I LeetCode Solution with the best time and space complexity. The solution to Maximum Frequency of an Element After Performing Operations I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximum Frequency of an Element After Performing Operations I solution in C++
4. Maximum Frequency of an Element After Performing Operations I solution in Java
5. Maximum Frequency of an Element After Performing Operations I solution in Python
6. Additional Resources

Problem Statement of Maximum Frequency of an Element After Performing Operations I

You are given an integer array nums and two integers k and numOperations.
You must perform an operation numOperations times on nums, where in each operation you:

Select an index i that was not selected in any previous operations.
Add an integer in the range [-k, k] to nums[i].

Return the maximum possible frequency of any element in nums after performing the operations.

Example 1:

Input: nums = [1,4,5], k = 1, numOperations = 2
Output: 2
Explanation:
We can achieve a maximum frequency of two by:

Adding 0 to nums[1]. nums becomes [1, 4, 5].
Adding -1 to nums[2]. nums becomes [1, 4, 4].

Example 2:

Input: nums = [5,11,20,20], k = 5, numOperations = 1
Output: 2
Explanation:
We can achieve a maximum frequency of two by:

Adding 0 to nums[1].

Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 105
0 <= k <= 105
0 <= numOperations <= nums.length

Complexity Analysis

• Time Complexity: O(n\log n)
• Space Complexity: O(n)

3346. Maximum Frequency of an Element After Performing Operations I LeetCode Solution in C++

class Solution {
 public:
  int maxFrequency(vector<int>& nums, int k, int numOperations) {
    int ans = 1;
    int adjustable = 0;
    unordered_map<int, int> count;
    map<int, int> line;
    set<int> candidates;

    for (const int num : nums) {
      ++count[num];
      ++line[num - k];
      --line[num + k + 1];
      candidates.insert(num);
      candidates.insert(num - k);
      candidates.insert(num + k + 1);
    }

    for (const int num : candidates) {
      adjustable += line.contains(num) ? line[num] : 0;
      const int countNum = count.contains(num) ? count[num] : 0;
      const int adjusted = adjustable - countNum;
      ans = max(ans, countNum + min(numOperations, adjusted));
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3346. Maximum Frequency of an Element After Performing Operations I LeetCode Solution in Java

class Solution {
  public int maxFrequency(int[] nums, int k, int numOperations) {
    int ans = 1;
    int adjustable = 0;
    Map<Integer, Integer> count = new HashMap<>();
    TreeMap<Integer, Integer> line = new TreeMap<>();
    TreeSet<Integer> candidates = new TreeSet<>();

    for (final int num : nums) {
      count.merge(num, 1, Integer::sum);
      line.merge(num - k, 1, Integer::sum);
      line.merge(num + k + 1, -1, Integer::sum);
      candidates.add(num);
      candidates.add(num - k);
      candidates.add(num + k + 1);
    }

    for (final int num : candidates) {
      adjustable += line.getOrDefault(num, 0);
      final int countNum = count.getOrDefault(num, 0);
      final int adjusted = adjustable - countNum;
      ans = Math.max(ans, countNum + Math.min(numOperations, adjusted));
    }

    return ans;
  }
}
// code provided by PROGIEZ

3346. Maximum Frequency of an Element After Performing Operations I LeetCode Solution in Python

from sortedcontainers import SortedDict


class Solution:
  def maxFrequency(self, nums: list[int], k: int, numOperations: int) -> int:
    ans = 1
    adjustable = 0
    count = collections.Counter(nums)
    line = SortedDict()
    candidates = set()

    for num in nums:
      line[num - k] = line.get(num - k, 0) + 1
      line[num + k + 1] = line.get(num + k + 1, 0) - 1
      candidates.add(num)
      candidates.add(num - k)
      candidates.add(num + k + 1)

    for num in sorted(candidates):
      adjustable += line.get(num, 0)
      adjusted = adjustable - count[num]
      ans = max(ans, count[num] + min(numOperations, adjusted))

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.