Maximum Frequency of an Element After Performing Operations II

Hard

#2973Time: O(N^3) or O(N^2) with optimizations. Sorting takes O(N log N). The nested loops run in O(N^2). Inside the inner loop, iterating through the window to test targets takes O(N) time, leading to O(N^3). This can be optimized to O(N^2) by efficiently querying counts, but it's still too slow for the given constraints.Space: O(N) in the worst case for the frequency map within the loops.

Patterns

Sliding Window Prefix Sum

Algorithms

Binary Search Sorting

Data structures

Array

Prompt

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:

Adding 0 to nums[1].

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
0 <= k <= 10⁹
0 <= numOperations <= nums.length

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves systematically checking every possible contiguous subarray within the sorted nums array. For each subarray, we evaluate if all its elements can be unified into a single target value, given the constraints on operations. The core idea is that if a group of m elements can be made equal, they must form a subsequence where the difference between the maximum and minimum element is at most 2*k. By sorting the array, we can focus on contiguous subarrays as candidates for such groups. For each subarray, we then try to find a suitable target value T among its own elements that minimizes the number of required operations and satisfies all problem conditions.

Algorithm

Sort the input array nums.
Initialize a variable maxFreq to 0, which will store the maximum possible frequency.
Iterate through all possible contiguous subarrays of nums. This can be done with two nested loops, with outer loop variable i from 0 to N-1 and inner loop variable j from i to N-1.
For each subarray W = nums[i...j], check if it's possible to make all its elements equal to a single value.
A necessary condition is that nums[j] - nums[i] <= 2*k. If this condition is violated, we can break the inner loop and advance i, as any further increase in j will also violate it.
If the condition holds, we need to find if there exists a target value T for this subarray. The best candidates for T are the elements within the subarray itself, as this maximizes the number of elements that don't need to be changed.
We iterate through each unique element x in the window nums[i...j] and test it as a potential target T.
For each potential target x, we first check if it's valid for the entire window: max(x - nums[i], nums[j] - x) <= k.
If x is a valid target, we calculate its frequency c within the window nums[i...j].
Let m = j - i + 1 be the size of the window. The number of operations required is m - c. We check if this is feasible with the given constraints: m - c <= numOperations and numOperations + c <= N (where N is the total number of elements).
If both constraints are satisfied, it means a frequency of m is achievable. We update maxFreq = max(maxFreq, m).
After checking all subarrays, maxFreq will hold the result.

Walkthrough

First, we sort the array nums to easily handle the condition max - min <= 2*k. After sorting, any subsequence that can be unified will be contained within a contiguous block nums[i...j] where nums[j] - nums[i] <= 2*k.

We use nested loops to consider every contiguous subarray nums[i...j]. For each subarray, we check if it's a candidate for unification. The length of this subarray, m = j - i + 1, is a potential frequency we can achieve.

To unify the elements of nums[i...j], we need a target T. A valid T must be reachable from every element in the subarray, meaning |T - nums[k]| <= k for all k from i to j. This is possible if and only if there's an overlap in the possible ranges, which simplifies to nums[j] - nums[i] <= 2*k.

Assuming this holds, we need to find a T that satisfies the operation constraints. The number of operations depends on how many elements are already equal to T. To minimize operations, we should choose a T that is already frequent in the subarray. The best candidates for T are the elements x present in nums[i...j]. For each such x, we check if it's a valid target for the whole subarray (max(x - nums[i], nums[j] - x) <= k). If it is, we count its occurrences c and check if the number of modifications m-c is within our budget (m-c <= numOperations) and if the leftover operations can be used on other elements (numOperations + c <= nums.length). If we find such a valid configuration, we update our maximum frequency found so far.

To implement this, we can use a frequency map for each window to count occurrences, leading to an overall O(N^2) complexity.

1import java.util.Arrays;2import java.util.HashMap;3 4class Solution {5    public int maxFrequency(int[] nums, int k, int numOperations) {6        int n = nums.length;7        Arrays.sort(nums);8        int maxFreq = 0;9 10        // Find initial frequency for the case of 0 operations11        if (n > 0) {12            int currentStreak = 1;13            maxFreq = 1;14            for (int i = 1; i < n; i++) {15                if (nums[i] == nums[i - 1]) {16                    currentStreak++;17                } else {18                    currentStreak = 1;19                }20                maxFreq = Math.max(maxFreq, currentStreak);21            }22        }23        if (numOperations == 0) return maxFreq;24 25        for (int i = 0; i < n; i++) {26            HashMap<Integer, Integer> counts = new HashMap<>();27            for (int j = i; j < n; j++) {28                if ((long)nums[j] - nums[i] > 2L * k) {29                    break;30                }31 32                counts.put(nums[j], counts.getOrDefault(nums[j], 0) + 1);33                int m = j - i + 1;34 35                // Try each element in the window as a target36                for (int p = i; p <= j; p++) {37                    int target = nums[p];38                    // Check if target is valid for the whole window39                    if (Math.max((long)target - nums[i], (long)nums[j] - target) <= k) {40                        int targetCount = counts.get(target);41                        if (m - targetCount <= numOperations && numOperations + targetCount <= n) {42                            maxFreq = Math.max(maxFreq, m);43                        }44                    }45                }46            }47        }48        return maxFreq;49    }50}

Complexity

Time

O(N^3) or O(N^2) with optimizations. Sorting takes O(N log N). The nested loops run in O(N^2). Inside the inner loop, iterating through the window to test targets takes O(N) time, leading to O(N^3). This can be optimized to O(N^2) by efficiently querying counts, but it's still too slow for the given constraints.

Space

O(N) in the worst case for the frequency map within the loops.

Trade-offs

Pros

It's a straightforward, brute-force-like approach that correctly explores the problem space based on the sorted array property.
It's easier to reason about and implement compared to more optimized and complex solutions.

Cons

The time complexity of O(N^2) can be too slow for the given constraints (N up to 10^5), likely resulting in a 'Time Limit Exceeded' error.

A more efficient approach is to change the perspective: instead of checking what frequency a subarray can achieve, let's fix a potential target value and calculate the maximum frequency we can achieve for it. The best candidates for a target value are the numbers already present in the array.

This approach iterates through each unique element x in the sorted nums array, treating it as the target T. For each T=x, we determine the maximum number of elements we can make equal to x. This number is determined by two factors: the number of operations available and the number of elements that are 'close enough' to x.

An element s is 'close enough' if it can be transformed into x by adding a value in [-k, k], which means s must be in the range [x-k, x+k]. In the sorted array, all such elements form a contiguous block. We can find this block efficiently using binary search.

The number of elements we can make equal to x is the sum of its original count (count_x) and the number of additional elements we can afford to change (numOperations). However, this is capped by the total number of 'close enough' elements we found. We also need to respect a more subtle constraint: the total number of operations must be performable on distinct indices, which leads to the condition numOperations + count_x <= nums.length.

Algorithm

Sort the input array nums.
Pre-calculate the frequency of each unique number in nums and store it in a map. This can be done in O(N) on the sorted array.
Initialize maxFreq to 0. If numOperations is 0, the answer is simply the highest frequency of any element, which can be found during pre-calculation.
Iterate through each unique element x in nums (e.g., by iterating through the keys of the frequency map). For each x, consider it as the target value T.
For a target T=x, retrieve its original frequency, count_x, from the map.
Check the constraint numOperations + count_x <= N. If this fails, it means we are forced to operate on elements we want to keep as x. In this case, the maximum frequency we can achieve for x is just count_x. Update maxFreq = max(maxFreq, count_x) and proceed to the next unique element.
If the constraint holds, find all elements in nums that can be converted to x. These are elements s where |x - s| <= k, which means s must be in the range [x - k, x + k].
In the sorted nums array, these candidate elements form a contiguous block. Use binary search (lower_bound and upper_bound) to find the start index l and end index r of this block.
The total number of candidates available to form the target x is numCandidates = r - l + 1.
With numOperations, we can change up to numOperations other elements into x. So, the potential frequency is count_x + numOperations.
This potential frequency is limited by the number of available candidates. Therefore, the maximum frequency achievable with x as the target is achievableFreq = min(count_x + numOperations, numCandidates).
Update maxFreq = max(maxFreq, achievableFreq).
After checking all unique elements as potential targets, maxFreq will hold the final answer.

Walkthrough

The algorithm begins by sorting the nums array in O(N log N) time. This allows for efficient searching and grouping of elements.

The core idea is to iterate through every unique number x present in nums and calculate the maximum frequency possible if x were the target value. For a chosen target x, we can form a group of m identical values by using its count_x original occurrences and converting m - count_x other numbers.

The number of operations required is m - count_x, which must be less than or equal to numOperations. This gives an upper bound on m: m <= count_x + numOperations.

The elements we convert must be transformable to x. An element s can be transformed to x if |s - x| <= k. All such convertible elements lie in the range [x-k, x+k]. Since nums is sorted, we can find the number of elements in this range in O(log N) time using two binary searches (one for the lower bound x-k and one for the upper bound x+k). Let this count be numCandidates.

The size of our final group m cannot be larger than numCandidates. Thus, we have another upper bound: m <= numCandidates.

Combining these, for a target x, the maximum frequency is min(count_x + numOperations, numCandidates). We also must satisfy the constraint that we have enough elements outside our target group to perform any leftover operations. This translates to numOperations + count_x <= N. If this is violated, we can only achieve a frequency of count_x.

We repeat this process for every unique element in nums and take the maximum frequency found. The overall time complexity will be O(N log N) because of the initial sort and the O(D log N) work in the loop, where D is the number of distinct elements (D <= N).

1import java.util.Arrays;2 3class Solution {4    public int maxFrequency(int[] nums, int k, int numOperations) {5        int n = nums.length;6        Arrays.sort(nums);7 8        int maxFreq = 0;9        if (n > 0) {10            int currentStreak = 0;11            for (int i = 0; i < n; i++) {12                if (i > 0 && nums[i] == nums[i-1]) {13                    currentStreak++;14                } else {15                    currentStreak = 1;16                }17                maxFreq = Math.max(maxFreq, currentStreak);18            }19        }20 21        int i = 0;22        while (i < n) {23            int j = i;24            while (j < n && nums[j] == nums[i]) {25                j++;26            }27            int count = j - i;28            long target = nums[i];29 30            if (numOperations + count <= n) {31                long minVal = target - k;32                long maxVal = target + k;33 34                int startIdx = lowerBound(nums, minVal);35                int endIdx = upperBound(nums, maxVal);36                37                int numCandidates = endIdx - startIdx;38                int achievableFreq = Math.min(count + numOperations, numCandidates);39                maxFreq = Math.max(maxFreq, achievableFreq);40            }41            i = j;42        }43 44        return maxFreq;45    }46 47    // Finds the first index >= val48    private int lowerBound(int[] arr, long val) {49        int low = 0, high = arr.length;50        while (low < high) {51            int mid = low + (high - low) / 2;52            if (arr[mid] >= val) {53                high = mid;54            } else {55                low = mid + 1;56            }57        }58        return low;59    }60 61    // Finds the first index > val62    private int upperBound(int[] arr, long val) {63        int low = 0, high = arr.length;64        while (low < high) {65            int mid = low + (high - low) / 2;66            if (arr[mid] > val) {67                high = mid;68            } else {69                low = mid + 1;70            }71        }72        return low;73    }74}

Complexity

Time

O(N log N). Sorting takes O(N log N). The main loop iterates through unique elements. For each unique element, it performs two binary searches, taking O(log N). In the worst case, all elements are unique, leading to O(N log N) for the loop. The total complexity is dominated by these two parts.

Space

O(1) or O(log N) depending on the sort implementation's space usage. The algorithm itself uses constant extra space.

Trade-offs

Pros

Highly efficient with O(N log N) time complexity, which passes the given constraints.
The logic is sound and covers all aspects of the problem's constraints once understood.

Cons

The logic relies on a subtle understanding of the problem's constraints, particularly how operations are counted and distributed.
Requires careful implementation of binary search (or using library functions) to avoid off-by-one errors.

Solutions

Solution

1class Solution {2public3  int maxFrequency(int[] nums, int k, int numOperations) {4    Map<Integer, Integer> cnt = new HashMap<>();5    TreeMap<Integer, Integer> d = new TreeMap<>();6    for (int x : nums) {7      cnt.merge(x, 1, Integer : : sum);8      d.putIfAbsent(x, 0);9      d.merge(x - k, 1, Integer : : sum);10      d.merge(x + k + 1, -1, Integer : : sum);11    }12    int ans = 0, s = 0;13    for (var e : d.entrySet()) {14      int x = e.getKey(), t = e.getValue();15      s += t;16      ans = Math.max(ans, Math.min(s, cnt.getOrDefault(x, 0) + numOperations));17    }18    return ans;19  }20}

1class Solution {2public:3  int maxFrequency(vector<int> &nums, int k, int numOperations) {4    unordered_map<int, int> cnt;5    map<int, int> d;6    for (int x : nums) {7      cnt[x]++;8      d[x];9      d[x - k]++;10      d[x + k + 1]--;11    }12    int ans = 0, s = 0;13    for (const auto &[x, t] : d) {14      s += t;15      ans = max(ans, min(s, cnt[x] + numOperations));16    }17    return ans;18  }19};

1class Solution:2    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 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.

← Previous

Previous problem

Next problem