3347. Maximum Frequency of an Element After Performing Operations II LeetCode Solution

In this guide, you will get 3347. Maximum Frequency of an Element After Performing Operations II LeetCode Solution with the best time and space complexity. The solution to Maximum Frequency of an Element After Performing Operations II 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 II solution in C++
  4. Maximum Frequency of an Element After Performing Operations II solution in Java
  5. Maximum Frequency of an Element After Performing Operations II solution in Python
  6. Additional Resources
3347. Maximum Frequency of an Element After Performing Operations II LeetCode Solution image

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

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], after which nums becomes [1, 4, 5].
Adding -1 to nums[2], after which 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:

See also  1090. Largest Values From Labels LeetCode Solution

Adding 0 to nums[1].

Constraints:

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

Complexity Analysis

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

3347. Maximum Frequency of an Element After Performing Operations II LeetCode Solution in C++

class Solution {
 public:
  // Same as 3346. Maximum Frequency of an Element After Performing Operations I
  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 */

3347. Maximum Frequency of an Element After Performing Operations II LeetCode Solution in Java

class Solution {
  // Same as 3346. Maximum Frequency of an Element After Performing Operations I
  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

3347. Maximum Frequency of an Element After Performing Operations II LeetCode Solution in Python

from sortedcontainers import SortedDict


class Solution:
  # Same as 3346. Maximum Frequency of an Element After Performing Operations I
  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

See also  930. Binary Subarrays With Sum LeetCode Solution

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