Maximum Frequency of an Element After Performing Operations II solution and explanation
Google
9 more videos on this problem
Maximum Frequency of an Element After Performing Operations II | Difference Array | Leetcode 3347codestorywithMIK · 30:31 · 12K views
3347 & 3346. Maximum Frequency of an Element After Performing Operations II Line SweepAryan Mittal · 24:25 · 11K views
Maximum Frequency of an Element After Performing Operations II | LeetCode 3347 | Line SweepSanyam IIT Guwahati · 27:32 · 1K views
3347. Maximum Frequency of an Element After Performing Operations II | Leetcode Daily - PythonLeetcode Daily · 9:14 · 529 views
Daily Leetcode #2031: Oct 22, 2025 - 3347. Maximum Frequency of an Element After Performing Op...Programming Live with Larry · 13:52 · 502 views
3347. Maximum Frequency of an Element After Performing Operations II (Leetcode Hard)Programming Live with Larry · 10:40 · 446 views
Maximum Frequency of an Element After Performing Operations II | LeetCode 3347 - Pythonimpoldev · 18:29 · 414 views
Leetcode 3347. Maximum Frequency of an Element After Performing Operations II | Binary Search PythonStatLearn Tech · 18:43 · 200 views
3347. Maximum Frequency of an Element After Performing Operations II | Leetcode Daily ChallengeEye on AI and DSA · 19:28 · 176 views
Maximum Frequency of an Element After Performing Operations II | LeetCode 3347 | Developer CoderDeveloper Coder · 22:02 · 143 views
The problem
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], after whichnumsbecomes[1, 4, 5]. - Adding -1 to
nums[2], after whichnumsbecomes[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] <= 1090 <= k <= 1090 <= 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.
def maxFrequency(nums, k, numOperations):
nums.sort()
total, res, left = 0, 0, 0
for right in range(len(nums)):
total += nums[right]
while nums[right] * (right - left + 1) > total + k:
total -= nums[left]
left += 1
res = max(res, right - left + 1)
return res
nums = [1, 4, 5]
k = 1
numOperations = 2
print(maxFrequency(nums, k, numOperations))import java.util.Arrays;
public class MaxFrequency {
public static int maxFrequency(int[] nums, int k, int numOperations) {
Arrays.sort(nums);
long total = 0;
int left = 0, result = 0;
for (int right = 0; right < nums.length; right++) {
total += nums[right];
while (nums[right] * (right - left + 1) > total + k) {
total -= nums[left];
left++;
}
result = Math.max(result, right - left + 1);
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 4, 5};
int k = 1;
int numOperations = 2;
System.out.println(maxFrequency(nums, k, numOperations));
}
}function maxFrequency(nums, k, numOperations) {
nums.sort((a, b) => a - b);
let total = 0, left = 0, result = 0;
for (let right = 0; right < nums.length; right++) {
total += nums[right];
while (nums[right] * (right - left + 1) > total + k) {
total -= nums[left];
left++;
}
result = Math.max(result, right - left + 1);
}
return result;
}
const nums = [1, 4, 5];
const k = 1;
const numOperations = 2;
console.log(maxFrequency(nums, k, numOperations));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int maxFrequency(int* nums, int numsSize, int k, int numOperations) {
qsort(nums, numsSize, sizeof(int), compare);
long long operations = 0, left = 0, result = 1;
for (long long right = 0; right < numsSize; ++right) {
operations += (long long)(nums[right] - nums[right - 1]) * (right - left);
while (operations > k) {
operations -= nums[right] - nums[left];
++left;
}
result = fmax(result, right - left + 1);
}
return (int)result;
}
int main() {
int nums[] = {1, 4, 5};
int k = 1;
int numOperations = 2;
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxFrequency(nums, size, k, numOperations));
return 0;
}using System;
public class MaxFrequencySolution {
public static int MaxFrequency(int[] nums, int k, int numOperations) {
Array.Sort(nums);
long total = 0;
int left = 0, result = 0;
for (int right = 0; right < nums.Length; right++) {
total += nums[right];
while (nums[right] * (right - left + 1) > total + k) {
total -= nums[left];
left++;
}
result = Math.Max(result, right - left + 1);
}
return result;
}
public static void Main() {
int[] nums = {1, 4, 5};
int k = 1;
int numOperations = 2;
Console.WriteLine(MaxFrequency(nums, k, numOperations));
}
}This Python solution sorts the array and utilizes a sliding window to determine the maximum frequency:
totalkeeps track of the sum of numbers in the current window.- For each
rightindex, check whether the window can be expanded if total operations needed are withink, else shrink window from left. - Result is updated whenever a larger valid window is found.
Time Complexity: O(n log n) due to sorting, where n is the number of elements in nums.
Space Complexity: O(1) as no extra space proportional to input size is used.
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.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxFrequency(vector<int>& nums, int k, int numOperations) {
sort(nums.begin(), nums.end());
long long operations = 0, left = 0, maxFreq = 1;
for (int right = 0; right < nums.size(); ++right) {
operations += nums[right];
while (nums[right] * (right - left + 1) > operations + k) {
operations -= nums[left++];
}
maxFreq = max(maxFreq, right - left + 1);
}
return maxFreq;
}
int main() {
vector<int> nums = {1, 4, 5};
int k = 1, numOperations = 2;
cout << maxFrequency(nums, k, numOperations) << endl;
return 0;
}function maxFrequency(nums, k, numOperations) {
nums.sort((a, b) => a - b);
let total = 0, left = 0, result = 0;
for (let right = 0; right < nums.length; right++) {
total += nums[right];
while (nums[right] * (right - left + 1) > total + k) {
total -= nums[left];
left++;
}
result = Math.max(result, right - left + 1);
}
return result;
}
// Example usage:
const nums = [1, 4, 5];
const k = 1;
const numOperations = 2;
console.log(maxFrequency(nums, k, numOperations));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.
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.
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
1at positionx-k, indicating that a new interval starts from this position. - Subtract
1at positionx+k+1, indicating that an interval ends from this position. - Add
0at positionx, ensuring that positionxexists 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
xappears in the original array, operations onxitself are meaningless. Therefore, there ares - cnt[x]other elements that can be changed toxthrough operations, but at mostnumOperationsoperations can be performed. So the maximum frequency at this position iscnt[x] + min(s - cnt[x], numOperations). - If
xdoes not appear in the original array, then at mostnumOperationsoperations can be performed to change other elements tox. Therefore, the maximum frequency at this position ismin(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.
function maxFrequency(nums: number[], k: number, numOperations: number): number {
const cnt: Record<number, number> = {};
const d: Record<number, number> = {};
for (const x of nums) {
cnt[x] = (cnt[x] || 0) + 1;
d[x] = d[x] || 0;
d[x - k] = (d[x - k] || 0) + 1;
d[x + k + 1] = (d[x + k + 1] || 0) - 1;
}
let [ans, s] = [0, 0];
const keys = Object.keys(d)
.map(Number)
.sort((a, b) => a - b);
for (const x of keys) {
s += d[x];
ans = Math.max(ans, Math.min(s, (cnt[x] || 0) + numOperations));
}
return ans;
}func maxFrequency(nums []int, k int, numOperations int) (ans int) {
cnt := make(map[int]int)
d := make(map[int]int)
for _, x := range nums {
cnt[x]++
d[x] = d[x]
d[x-k]++
d[x+k+1]--
}
s := 0
keys := make([]int, 0, len(d))
for key := range d {
keys = append(keys, key)
}
sort.Ints(keys)
for _, x := range keys {
s += d[x]
ans = max(ans, min(s, cnt[x]+numOperations))
}
return
}use std::collections::{HashMap, BTreeMap};
impl Solution {
pub fn max_frequency(nums: Vec<i32>, k: i32, num_operations: i32) -> i32 {
let mut cnt = HashMap::new();
let mut d = BTreeMap::new();
for &x in &nums {
*cnt.entry(x).or_insert(0) += 1;
d.entry(x).or_insert(0);
*d.entry(x - k).or_insert(0) += 1;
*d.entry(x + k + 1).or_insert(0) -= 1;
}
let mut ans = 0;
let mut s = 0;
for (&x, &t) in d.iter() {
s += t;
let cur = s.min(cnt.get(&x).copied().unwrap_or(0) + num_operations);
ans = ans.max(cur);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Technique | Time Complexity: O(n log n) due to sorting, where n is the number of elements in nums. Space Complexity: O(1) as no extra space proportional to input size is used. |
| 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 | – |
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. |
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.