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.
The brute-force approach is slow because for each candidate target, we scan the entire array. We can optimize this calculation by first sorting the nums array. Once the array is sorted, counting elements within a specific range [minVal, maxVal] can be done much faster than a linear scan.
By using binary search, we can find the number of elements in the range [target - k, target + k] in O(log N) time. We can implement helper functions like lower_bound and upper_bound to find the start and end of this range in the sorted array. The rest of the logic remains the same: generate candidate targets, and for each, calculate the achievable frequency. The frequency of each number can also be pre-computed and stored in a hash map to speed up lookups for exactMatches.
Algorithm
- First, sort the input array
nums. - Generate the same set of candidate targets as in the brute-force approach:
nums[i],nums[i]-k, andnums[i]+kfor alli. - Pre-calculate the frequency of each number in
numsand store it in a hash map for O(1) lookup. - Iterate through each
targetin the candidate set: a. GetexactMatchesfor thetargetfrom the frequency map. b. The key optimization is to find the count of numbers in the range[target - k, target + k]efficiently. Sincenumsis sorted, we can do this inO(log N)time using binary search. We find the index of the first element greater thantarget + k(upper_bound) and the index of the first element greater than or equal totarget - k(lower_bound). The difference between these indices gives therangeCount. c.possibleMatches = rangeCount - exactMatches. d.currentFreq = exactMatches + min(numOperations, possibleMatches). e. Update the overallmaxFreq. - Return
maxFreq.
Walkthrough
import java.util.Arrays;import java.util.HashMap;import java.util.HashSet;import java.util.Map;import java.util.Set; class Solution { public int maxFrequency(int[] nums, int k, int numOperations) { Arrays.sort(nums); Set<Long> candidates = new HashSet<>(); for (int num : nums) { candidates.add((long) num); candidates.add((long) num - k); candidates.add((long) num + k); } Map<Integer, Integer> freqMap = new HashMap<>(); for (int num : nums) { freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); } int maxFreq = 0; for (long target : candidates) { int exactMatches = freqMap.getOrDefault((int) target, 0); long low = target - k; long high = target + k; int startIdx = lower_bound(nums, low); int endIdx = upper_bound(nums, high); int rangeCount = endIdx - startIdx; int possibleMatches = rangeCount - exactMatches; int currentFreq = exactMatches + Math.min(numOperations, possibleMatches); maxFreq = Math.max(maxFreq, currentFreq); } return maxFreq; } private int lower_bound(int[] nums, long val) { int l = 0, r = nums.length; while (l < r) { int mid = l + (r - l) / 2; if (nums[mid] >= val) { r = mid; } else { l = mid + 1; } } return l; } private int upper_bound(int[] nums, long val) { int l = 0, r = nums.length; while (l < r) { int mid = l + (r - l) / 2; if (nums[mid] > val) { r = mid; } else { l = mid + 1; } } return l; }}Complexity
Time
O(N log N). Sorting takes O(N log N). Generating candidates takes O(N). The main loop runs O(N) times, and each iteration takes O(log N) for binary search. So, the total time is dominated by O(N log N).
Space
O(N) for storing candidates, the frequency map, and the sorted copy of the array (if not sorted in-place).
Trade-offs
Pros
Significantly faster than the brute-force approach.
Efficient enough to pass the time limits for the given constraints.
Cons
The number of candidates can still be large (O(N)), so the loop runs many times.
While better than O(N^2), it might not be the most optimal solution possible.
This approach provides a more fine-grained analysis to optimize the calculation. We split the problem into two cases based on the optimal target value T.
Case 1: The optimal target T is one of the numbers present in the input array nums.
We can iterate through each unique value v in nums and calculate the maximum frequency achievable with v as the target. After sorting nums, we can find the count of elements in [v-k, v+k] for all unique v efficiently using a two-pointer approach in O(N) time, which is better than repeated binary searches.
Case 2: The optimal target T is not a number present in nums.
In this case, the number of exact matches C(T) is 0. The formula for frequency becomes min(R(T), numOperations). To maximize this, we need to find the maximum possible value of R(T), which is the maximum number of elements that can fall into any window of size 2k. This is a classic maximum interval overlap problem, solvable with a sweep-line algorithm. By creating start and end events for each interval [num-k, num+k], we can find the point of maximum overlap.
The final answer is the maximum of the frequencies found in these two cases. The overall time complexity is dominated by the initial sort of nums.
Algorithm
- The achievable frequency for a target
Tisf(T) = min(R(T), C(T) + numOperations), whereR(T)is the count ofnumsin[T-k, T+k]andC(T)is the count ofnumsequal toT. - The maximum of
f(T)occurs either whenTis one of the values innums, or at a point whereR(T)is maximized (in which caseC(T)=0). - Sort
nums. This takesO(N log N). - Part A: Calculate max frequency for targets
Tinnums. a. Get unique sorted values fromnumsand their frequencies (C(T)). b. For each uniqueT, calculateR(T). Instead of repeated binary searches, use a two-pointer/sliding window approach on the sortednumsarray. AsTiterates through unique values, the window[T-k, T+k]slides. This allows calculating allR(T)values inO(N)total time. c. Computef(T)for each uniqueTand find the maximum, let's call itmaxFreqAtNum. - Part B: Calculate max frequency for targets
Tnot innums. a. This simplifies tomin(max_T R(T), numOperations). b.max_T R(T)is the problem of finding the maximum overlap among intervals[num-k, num+k]for allnuminnums. c. This can be solved with a sweep-line algorithm. Create event points(num-k, +1)and(num+k+1, -1). Sort these events and sweep through them, keeping track of the active interval count. The maximum count ismax_T R(T). d. Sincenumsis sorted, the start pointsnum-kand end pointsnum+k+1are also sorted. We can merge them inO(N)time to find the max overlap without a full sort of events. - The final answer is the maximum of the results from Part A and Part B.
Walkthrough
import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.TreeMap; class Solution { public int maxFrequency(int[] nums, int k, int numOperations) { int n = nums.length; if (n == 0) return 0; Arrays.sort(nums); // Part 1: Calculate max frequency for targets T that are present in nums Map<Integer, Integer> freqMap = new HashMap<>(); List<Integer> uniqueNums = new ArrayList<>(); uniqueNums.add(nums[0]); freqMap.put(nums[0], 1); for (int i = 1; i < n; i++) { if (nums[i] != nums[i - 1]) { uniqueNums.add(nums[i]); } freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1); } int maxFreqAtNum = 0; int l = 0, r = 0; for (int target : uniqueNums) { long minVal = (long) target - k; long maxVal = (long) target + k; while (l < n && nums[l] < minVal) { l++; } while (r < n && nums[r] <= maxVal) { r++; } int rangeCount = r - l; int exactMatches = freqMap.get(target); int possibleMatches = rangeCount - exactMatches; maxFreqAtNum = Math.max(maxFreqAtNum, exactMatches + Math.min(numOperations, possibleMatches)); } // Part 2: Calculate max frequency for targets T not in nums // This is min(max_T R(T), numOperations) Map<Long, Integer> sweep = new TreeMap<>(); for (int num : nums) { long start = (long) num - k; long end = (long) num + k; sweep.put(start, sweep.getOrDefault(start, 0) + 1); sweep.put(end + 1, sweep.getOrDefault(end + 1, 0) - 1); } int maxRangeCount = 0; int currentRangeCount = 0; for (int count : sweep.values()) { currentRangeCount += count; maxRangeCount = Math.max(maxRangeCount, currentRangeCount); } int maxFreqBetweenNums = Math.min(maxRangeCount, numOperations); return Math.max(maxFreqAtNum, maxFreqBetweenNums); }}Complexity
Time
O(N log N). Sorting `nums` takes O(N log N). Part A (two-pointers) takes O(N). Part B (sweep-line with TreeMap) takes O(N log N) due to map insertions. If implemented with sorted arrays and merging for the sweep-line, it would be O(N). The bottleneck remains the initial sort.
Space
O(N) for storing unique numbers, frequencies, and sweep-line events.
Trade-offs
Pros
Most efficient approach with O(N log N) complexity.
Breaks down the problem into logical subproblems that can be solved optimally.
The linear-time components (two-pointers, sweep-line after sort) make it fast in practice.
Cons
More complex to understand and implement correctly compared to the previous approaches.
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; }}class Solution { public: int maxFrequency ( vector < int >& nums , int k , int numOperations ) { unordered_map < int , int > cnt ; map < int , int > d ; for ( int x : nums ) { cnt [ x ] ++ ; d [ x ]; d [ x - k ] ++ ; d [ x + k + 1 ] -- ; } int ans = 0 , s = 0 ; for ( const auto & [ x , t ] : d ) { s += t ; ans = max ( ans , min ( s , cnt [ x ] + numOperations )); } return ans ; } };class Solution: def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int: cnt = defaultdict(int) d = defaultdict(int) for x in nums: cnt[x] += 1 d[x] += 0 d[x - k] += 1 d[x + k + 1] -= 1 ans = s = 0 for x, t in sorted(d . items()): s += t ans = max(ans, min(s, cnt[x] + numOperations)) return ansVideo 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.