Skip to main content
Talentd

Maximum Frequency of an Element After Performing Operations I - Solution & Explanation

MediumArrayBinary SearchSliding WindowSorting27 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

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]. nums becomes [1, 4, 5].
  • Adding -1 to 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:

  • Adding 0 to nums[1].

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 0 <= k <= 105
  • 0 <= numOperations <= nums.length

Approach Overview

Problem 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 1: Approach 1: Sliding Window Technique

The sliding window technique can be utilized here to keep track of a window of elements that can be turned into the same value by using the allowed operations efficiently.

Sort the array first, then utilize a variable to track the cost of making elements within the current window equal. Expand the window while the cost is within the allowed operations, and shrink the window otherwise.

Here, we use a sliding window strategy. By sorting the input array, we calculate a cost to bring each window of elements to the same value by adding or subtracting using available operations. We adjust the window size effectively to stay within the given operations limit to maximize the frequency.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to the sorting operation. Space Complexity: O(1), as no extra space is used besides input sorting itself.

Try this approach in the editor →

Approach 2: Approach 2: Binary Search with Prefix Sum

Another approach to solve this problem is using Binary Search combined with computing prefix sums. We attempt to make each element the highest frequency possible by using binary search on frequency and verify using prefix sum to ensure that allowed operations suffice to make all elements in range equal.

By prefix sum and binary search, checking the frequency transformable within the limit of allowed operations is done. This involves iterating through and checking transformations using the prefix sum accumulated to aid efficient calculation of needed operations per hypothetical frequency.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log m), where m is the max element - due to binary search. Space Complexity: O(n) for storing prefix sum.

Try this approach in the editor →

Approach 3: Difference Array

According to the problem description, for each element x in the array nums, we can change it to any integer within the range [x-k, x+k]. We want to perform operations on some elements in nums to maximize the frequency of a certain integer in the array.

The problem can be transformed into merging all elements in the interval [x-k, x+k] corresponding to each element x, and finding the integer that contains the most original elements in the merged intervals. This can be implemented using a difference array.

We use a dictionary d to record the difference array. For each element x, we perform the following operations on the difference array:

  • Add 1 at position x-k, indicating that a new interval starts from this position.
  • Subtract 1 at position x+k+1, indicating that an interval ends from this position.
  • Add 0 at position x, ensuring that position x exists in the difference array for subsequent calculations.

At the same time, we need to record the number of occurrences of each element in the original array, using a dictionary cnt to implement this.

Next, we perform prefix sum calculation on the difference array to get how many intervals cover each position. For each position x, we calculate the number of intervals covering it as s. Then we discuss by cases:

  • If x appears in the original array, operations on x itself are meaningless. Therefore, there are s - cnt[x] other elements that can be changed to x through operations, but at most numOperations operations can be performed. So the maximum frequency at this position is cnt[x] + min(s - cnt[x], numOperations).
  • If x does not appear in the original array, then at most numOperations operations can be performed to change other elements to x. Therefore, the maximum frequency at this position is min(s, numOperations).

Combining the above two cases, we can uniformly express it as min(s, cnt[x] + numOperations).

Finally, we traverse all positions, calculate the maximum frequency at each position, and take the maximum value among them as the answer.

The time complexity is O(n times log n) and the space complexity is O(n), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sliding Window Technique

Time Complexity: O(n log n), due to the sorting operation. Space Complexity: O(1), as no extra space is used besides input sorting itself.

Approach 2: Binary Search with Prefix Sum

Time Complexity: O(n log m), where m is the max element - due to binary search. Space Complexity: O(n) for storing prefix sum.

Difference Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window TechniqueO(n log n)O(1)Best general solution after sorting; efficient when scanning contiguous convertible ranges
Binary Search with Prefix SumO(n log n)O(n)Useful when evaluating each element as a target with fast range counting

Video Solution

Maximum Frequency of an Element After Performing Operations I | Made Easy | Leetcode 3346 • codestorywithMIK • 15,215 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Frequency of an Element After Performing Operations I easy or hard?
The problem is rated Medium because the core logic requires recognizing that sorting enables a range-based sliding window solution. The implementation is straightforward once the window condition and operation limit are understood.
Maximum Frequency of an Element After Performing Operations I Python/Java solution
Both Python and Java implementations typically start by sorting the array and then applying a sliding window to track the maximum group of elements that can be converted to the same value. The logic uses two pointers and a counter for how many operations are required within the window.
How to solve Maximum Frequency of an Element After Performing Operations I in O(n)?
A pure O(n) solution is not practical because the array must usually be sorted to efficiently group values that fall within the allowed adjustment range. After sorting, a sliding window scans the array once, giving O(n log n) overall complexity. The linear pass maintains the largest valid window of convertible elements.
What is the best approach for Maximum Frequency of an Element After Performing Operations I?
The sliding window approach after sorting the array is typically the best solution. It scans the array with two pointers and maintains a window of values that can be converted to a common target within the allowed operation range. The approach runs in O(n log n) time due to sorting and uses O(1) extra space.
Is Maximum Frequency of an Element After Performing Operations I asked at Google/Amazon/Meta?
Problems involving frequency maximization, sliding window ranges, and array transformations frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this problem test sorting, two‑pointer techniques, and reasoning about limited operations.
What data structure is used in Maximum Frequency of an Element After Performing Operations I?
The solution mainly relies on arrays combined with algorithmic techniques such as sorting, sliding window, and binary search. Some implementations also use a prefix sum array to quickly compute counts within value ranges.
What is the time complexity of Maximum Frequency of an Element After Performing Operations I?
The optimal solutions run in O(n log n) time. The log n factor comes from sorting the array or performing binary searches, while the window traversal itself is linear. Space complexity ranges from O(1) for the sliding window method to O(n) when prefix sums are used.

Ready to solve this problem?

Practice Maximum Frequency of an Element After Performing Operations I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Elements With Maximum Frequency

Next

Frequency of the Most Frequent Element