Maximum Frequency of an Element After Performing Operations I
MedPrompt
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
ithat was not selected in any previous operations. - Add an integer in the range
[-k, k]tonums[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].numsbecomes[1, 4, 5]. - Adding -1 to
nums[2].numsbecomes[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 <= 1051 <= nums[i] <= 1050 <= k <= 1050 <= numOperations <= nums.length
Approaches
3 approaches with complexity analysis and trade-offs.
This approach is based on the idea of testing a set of potential 'target' values that the elements of nums could be converted to. For any given target value T, we can calculate the maximum frequency we can achieve for it. The final answer will be the maximum frequency found across all possible target values.
The core of this method is to determine which values of T are worth checking. The number of elements that can be transformed into T depends on the range [T-k, T+k]. The count of elements within this range only changes when the boundaries T-k or T+k cross an element nums[i], or when T itself crosses an element nums[i]. This implies that the optimal T must be one of nums[i], nums[i]-k, or nums[i]+k for some i. Therefore, we can limit our search to this set of candidate values.
For each candidate target, we iterate through the entire nums array to count how many elements are already equal to the target (exactMatches) and how many can be changed to the target (possibleMatches). With numOperations available, we can convert min(numOperations, possibleMatches) elements. The total frequency for that target is the sum of exactMatches and the number of converted elements.
Algorithm
- Identify a set of candidate target values. A crucial observation is that an optimal target value
Tmust be 'close' to the numbers in the input array. A comprehensive set of candidates includesnums[i],nums[i] - k, andnums[i] + kfor every elementnums[i]in the array. This is because the function we are trying to maximize changes its value only at these points. - Store these candidate values in a
Setto handle duplicates. - Initialize a variable
maxFreqto 0. - Iterate through each
targetin the set of candidates: a. For the currenttarget, calculate the number of elements that can be made equal to it. We need two counts: i.exactMatches: The number of elements innumsthat are already equal totarget. ii.possibleMatches: The number of elementsnuminnumssuch thatnum != targetbut|num - target| <= k. These elements can be converted totargetusing one operation. b. The total frequency for the currenttargetisexactMatches + min(numOperations, possibleMatches). We can use up tonumOperationsto convert thepossibleMatches. c. UpdatemaxFreq = max(maxFreq, currentFreq). - After checking all candidates,
maxFreqwill hold the result.
Walkthrough
import java.util.HashSet;import java.util.Set; class Solution { public int maxFrequency(int[] nums, int k, int numOperations) { Set<Long> candidates = new HashSet<>(); for (int num : nums) { candidates.add((long) num); candidates.add((long) num - k); candidates.add((long) num + k); } int maxFreq = 0; for (long target : candidates) { int exactMatches = 0; int possibleMatches = 0; for (int num : nums) { if (num == target) { exactMatches++; } else if (Math.abs(num - target) <= k) { possibleMatches++; } } int currentFreq = exactMatches + Math.min(numOperations, possibleMatches); maxFreq = Math.max(maxFreq, currentFreq); } return maxFreq; }}Complexity
Time
O(N^2), where N is the number of elements in `nums`. The number of candidate targets can be up to O(N). For each candidate, we iterate through the entire `nums` array, which takes O(N) time. This results in a total time complexity of O(N) * O(N) = O(N^2).
Space
O(N), where N is the number of elements in `nums`. This is for storing the candidate target values in a set. In the worst case, there can be up to 3N distinct candidates.
Trade-offs
Pros
Simple to understand and implement.
Correctly identifies the necessary set of candidate target values to check.
Cons
The time complexity of O(N*C) where C is the number of candidates (up to 3N) makes it too slow for the given constraints (N up to 10^5), leading to a Time Limit Exceeded error.
Solutions
Solution
class Solution {public int maxFrequency(int[] nums, int k, int numOperations) { Map<Integer, Integer> cnt = new HashMap<>(); TreeMap<Integer, Integer> d = new TreeMap<>(); for (int x : nums) { cnt.merge(x, 1, Integer : : sum); d.putIfAbsent(x, 0); d.merge(x - k, 1, Integer : : sum); d.merge(x + k + 1, -1, Integer : : sum); } int ans = 0, s = 0; for (var e : d.entrySet()) { int x = e.getKey(), t = e.getValue(); s += t; ans = Math.max(ans, Math.min(s, cnt.getOrDefault(x, 0) + numOperations)); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.