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

Q: Is Maximum Frequency of an Element After Performing Operations II easy or hard?

The problem is categorized as Hard because it requires combining multiple techniques such as sorting, sliding window optimization, and cost calculations using prefix sums or arithmetic reasoning. The implementation is concise once the idea is understood, but discovering the correct window strategy can be challenging.

Q: Maximum Frequency of an Element After Performing Operations II Python/Java solution

Python and Java implementations usually follow the same pattern: sort the array, maintain a running sum or cost of the current window, and expand the right pointer while shrinking the left pointer when the operation limit is exceeded. This keeps the window valid and tracks the maximum frequency found.

Q: How to solve Maximum Frequency of an Element After Performing Operations II in O(n)?

Pure O(n) time is generally not achievable because sorting is required to efficiently group values that can be transformed into the same target. After sorting, a sliding window scans the array in linear time while tracking operation cost. The overall complexity therefore becomes O(n log n).

Q: What is the best approach for Maximum Frequency of an Element After Performing Operations II?

The most effective solution uses sorting combined with a sliding window. After sorting the array, expand a window while tracking the cost required to convert all elements inside the window to the current target value. If the cost exceeds the allowed operations, move the left pointer to restore feasibility. This approach runs in O(n log n) time due to sorting and O(1) extra space.

Q: Is Maximum Frequency of an Element After Performing Operations II asked at Google/Amazon/Meta?

Variants of this problem appear in interviews at companies like Google, Amazon, and Meta because it tests multiple skills at once: sorting, sliding window optimization, greedy reasoning, and prefix sum cost calculation. Interviewers expect candidates to move from a brute force idea to an optimized window-based solution.

Q: What data structure is used in Maximum Frequency of an Element After Performing Operations II?

The main structures used are arrays with sorting, two pointers for the sliding window, and optionally prefix sums for constant-time range cost queries. Some implementations also rely on frequency counting and binary search to determine valid window boundaries efficiently.

Q: What is the time complexity of Maximum Frequency of an Element After Performing Operations II?

The optimal solution runs in O(n log n) time because the array must be sorted before applying the sliding window or binary search technique. Once sorted, the window expansion or prefix calculations run in linear time. Space complexity ranges from O(1) for the sliding window approach to O(n) when prefix sums are used.

HardArray Binary Search Sliding Window Sorting26 min readAsked at: Amazon, Google, Bloomberg

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], 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

Approach Overview

Problem Overview: You are given an array where operations can adjust values within a certain range. The goal is to maximize the frequency of a single element after performing at most k operations. Each operation allows modifying values so that multiple elements can be aligned to the same target value.

The challenge is determining which value should become the target and how many surrounding elements can be transformed into it while staying within the allowed operation budget. Efficient solutions rely on sorting, range counting, and window-based cost tracking.

Approach 1: Sliding Window Technique (Sorting + Prefix Cost Tracking) (Time: O(n log n), Space: O(1))

Sort the array so values are processed in increasing order. Once sorted, treat each value as a potential target and expand a sliding window that represents elements you want to convert to this target. As the right pointer grows, compute the cost required to raise all elements in the window to match the current value. If the cost exceeds the allowed operations, shrink the window from the left.

The key insight: after sorting, the cheapest way to increase frequency is to raise smaller elements toward a larger target. Maintaining a running window lets you check feasibility in constant time per step. This approach combines sorting with a classic sliding window pattern to efficiently track the maximum achievable frequency.

Approach 2: Greedy with Frequency Count (Binary Search + Prefix Sum) (Time: O(n log n), Space: O(n))

This method focuses on evaluating each unique value as a potential target. After sorting the array, build prefix sums so the cost of converting a range can be computed instantly. For each index, use binary search to determine the farthest left boundary where the cost to convert all numbers to the current value does not exceed the allowed operations.

The prefix sums allow quick computation of the total increments required to raise a subarray to the target value. Greedy reasoning ensures that expanding toward smaller values gives the largest possible group. This approach blends prefix sum range calculations with binary search to efficiently test valid windows.

Recommended for interviews: The sliding window solution is typically expected. It demonstrates strong understanding of sorted array properties, two‑pointer window expansion, and incremental cost maintenance. A brute force approach would check every possible target and range, which quickly becomes quadratic. Showing that baseline reasoning helps, but implementing the optimized sliding window proves algorithmic maturity.

Approach 1: Sliding Window Technique

This approach leverages a sorted array and the sliding window approach to maximize the frequency of elements. The idea is to use the sliding window to keep track of a subarray where you can potentially make all elements equal by performing add operations within the given range [-k, k].

You maintain a window that only expands when the needed operations are within the limit specified by numOperations. This involves checking the operations needed to turn the smallest element in the window into the largest element and adjusting it as necessary to stretch the window.

The C code uses quick-sort to sort the array and then applies a sliding window to calculate the maximum frequency of any number that can be achieved by performing operations. The steps:

Sort the array.
Use a loop with two pointers left and right to maintain the window.
Calculate operations needed to make all numbers in this window equal to the number at the right pointer index and adjust the left pointer accordingly.
Continuously update the result with the maximum window size encountered.

Code

C Python Java C#JavaScript

Python

Java

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting, where n is the number of elements in the array.

Space Complexity: O(1) because modification is done in place.

Try this approach in the editor →

Approach 2: Greedy with Frequency Count

This approach focuses on efficiently maximizing the frequency using a greedy strategy with a series of modifications limited by numOperations. It involves selectively manipulating elements to bunch them toward an optimal frequency level after sorting the array.

The process aims to utilize available changes strategically for maximizing occurrences of a particular value obtained.

The C++ code example applies sorting followed by greedy decision making:

First, sort the array.
Utilize a slipping window by maximizing frequencies with allowable operation limitations calculated during traversal.
The sliding window shrinks when current needed operations for uniformity exceed specified k.
Use comparisons to update maximum frequency efficiently.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(n log n) due to sort operation as largest part.

Space Complexity: O(1) as changes are internal within the input collection.

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

Python Java C++Go TypeScript Rust C#

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Sliding Window Technique	Time Complexity: O(n log n) due to sorting, where n is the number of elements in the array. Space Complexity: O(1) because modification is done in place.
Greedy with Frequency Count	Time Complexity: O(n log n) due to sort operation as largest part. Space Complexity: O(1) as changes are internal within the input collection.
Difference Array	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Sliding Window Technique (Sorted Array)	O(n log n)	O(1)	Best general solution after sorting. Efficient for large arrays and common interview expectation.
Greedy with Prefix Sum + Binary Search	O(n log n)	O(n)	Useful when prefix sums are already available or when analyzing valid ranges via binary search.
Naive Range Checking (Conceptual Baseline)	O(n^2)	O(1)	Only helpful for understanding the brute force idea before optimizing.

Video Solution

Maximum Frequency of an Element After Performing Operations II | Difference Array | Leetcode 3347 • codestorywithMIK • 12,293 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Frequency of an Element After Performing Operations II easy or hard?

The problem is categorized as Hard because it requires combining multiple techniques such as sorting, sliding window optimization, and cost calculations using prefix sums or arithmetic reasoning. The implementation is concise once the idea is understood, but discovering the correct window strategy can be challenging.

Maximum Frequency of an Element After Performing Operations II Python/Java solution

Python and Java implementations usually follow the same pattern: sort the array, maintain a running sum or cost of the current window, and expand the right pointer while shrinking the left pointer when the operation limit is exceeded. This keeps the window valid and tracks the maximum frequency found.

How to solve Maximum Frequency of an Element After Performing Operations II in O(n)?

Pure O(n) time is generally not achievable because sorting is required to efficiently group values that can be transformed into the same target. After sorting, a sliding window scans the array in linear time while tracking operation cost. The overall complexity therefore becomes O(n log n).

What is the best approach for Maximum Frequency of an Element After Performing Operations II?

The most effective solution uses sorting combined with a sliding window. After sorting the array, expand a window while tracking the cost required to convert all elements inside the window to the current target value. If the cost exceeds the allowed operations, move the left pointer to restore feasibility. This approach runs in O(n log n) time due to sorting and O(1) extra space.

Is Maximum Frequency of an Element After Performing Operations II asked at Google/Amazon/Meta?

Variants of this problem appear in interviews at companies like Google, Amazon, and Meta because it tests multiple skills at once: sorting, sliding window optimization, greedy reasoning, and prefix sum cost calculation. Interviewers expect candidates to move from a brute force idea to an optimized window-based solution.

What data structure is used in Maximum Frequency of an Element After Performing Operations II?

The main structures used are arrays with sorting, two pointers for the sliding window, and optionally prefix sums for constant-time range cost queries. Some implementations also rely on frequency counting and binary search to determine valid window boundaries efficiently.

What is the time complexity of Maximum Frequency of an Element After Performing Operations II?

The optimal solution runs in O(n log n) time because the array must be sorted before applying the sliding window or binary search technique. Once sorted, the window expansion or prefix calculations run in linear time. Space complexity ranges from O(1) for the sliding window approach to O(n) when prefix sums are used.

Ready to solve this problem?

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

Practice on FleetCode

Count Elements With Maximum Frequency

Frequency of the Most Frequent Element

Problem Info

DifficultyHard

Acceptance53.8%

Approaches3

Reading time26 min

Asked at

Amazon Google Bloomberg

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Sliding Window Technique

Code

Complexity

Approach 2: Greedy with Frequency Count

Code

Complexity

Approach 3: Difference Array

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents