Watch 10 video solutions for Maximum Frequency of an Element After Performing Operations I, a medium level problem involving Array, Binary Search, Sliding Window. This walkthrough by codestorywithMIK has 14,421 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
i that was not selected in any previous operations.[-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:
nums[1]. nums becomes [1, 4, 5].nums[2]. 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:
nums[1].
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1050 <= k <= 1050 <= numOperations <= nums.lengthProblem Overview: You are given an array and allowed to perform a limited number of operations where an element can be adjusted within a fixed range. The goal is to maximize how many elements can become equal to the same value after using at most numOperations. The challenge is identifying which value to target and how many nearby elements can be transformed to match it.
Approach 1: Sliding Window Technique (Sorting + Two Pointers) (Time: O(n log n), Space: O(1))
Start by sorting the array so elements close in value are adjacent. For a chosen target value, any number within the range [target - k, target + k] can potentially be converted to that value with one operation. Use a sliding window with two pointers to maintain a segment where the difference between the current element and the left boundary stays within 2 * k. This window represents values that can potentially converge to a single number. Track how many elements in the window already equal the target and how many require operations. If required operations exceed numOperations, shrink the window. This approach works well because sorting converts the range constraint into a contiguous window problem and allows efficient expansion and contraction using the sliding window pattern.
Approach 2: Binary Search with Prefix Sum (Time: O(n log n), Space: O(n))
Another strategy is to fix a candidate target and determine how many elements can be converted to it. After sorting the array, build a prefix sum array to quickly count elements in ranges. For each index, use binary search to find the boundaries of values within [nums[i] - k, nums[i] + k]. This gives the maximum set of numbers that could potentially become nums[i]. Some of them may already equal the target, while the rest require operations. Since only numOperations changes are allowed, the achievable frequency is existing + min(numOperations, convertible). Prefix sums help compute counts instantly, while binary search finds valid ranges in O(log n). The technique combines sorting, range queries, and binary search to efficiently evaluate each candidate value.
Recommended for interviews: The sliding window solution is typically preferred. It demonstrates strong pattern recognition and avoids repeated binary searches. Interviewers often expect candidates to sort the array and maintain a dynamic window of convertible values. The binary search + prefix sum method is still valid and shows a solid understanding of range queries and precomputation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Technique | O(n log n) | O(1) | Best general solution after sorting; efficient when scanning contiguous convertible ranges |
| Binary Search with Prefix Sum | O(n log n) | O(n) | Useful when evaluating each element as a target with fast range counting |