Skip to content

3347. Maximum Frequency of an Element After Performing Operations II 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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