Maximum Frequency of an Element After Performing Operations I solution and explanation
Google
9 more videos on this problem
Maximum Frequency of an Element After Performing Operations I | Made Easy | Leetcode 3346codestorywithMIK · 37:48 · 15K 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 I | LeetCode 3346 | Prefix SumSanyam IIT Guwahati · 17:49 · 4K views
Leetcode 3346 | Maximum Frequency of an Element After Performing Operations I | Biweekly Contest 143Road To FAANG · 11:26 · 3K views
3346. Maximum Frequency of an Element After Performing Operations I | Leetcode Daily - PythonLeetcode Daily · 7:56 · 2K views
Daily Leetcode #2030: Oct 21, 2025 - 3346. Maximum Frequency of an Element After Performing Ops..Programming Live with Larry · 25:42 · 1K views
py3 C++ Line sweep解Leetcode 3346 Maximum Frequency of an Element After Performing Operations IAn-Wen Deng · 12:57 · 956 views
3346. Maximum Frequency of an Element After Performing Operations I (Leetcode Medium)Programming Live with Larry · 24:06 · 907 views
Maximum Frequency of an Element After Performing Operations I | LeetCode 3346 | Developer CoderDeveloper Coder · 27:13 · 636 views
Maximum Frequency of an Element After Performing Operations I | LeetCode 3346 - Pythonimpoldev · 18:41 · 529 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].numsbecomes[1, 4, 5]. - Adding -1 to
nums[2].numsbecomes[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] <= 1050 <= k <= 1050 <= 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.
def maxFrequency(nums, k, numOperations):
nums.sort()
left = 0
max_freq = 0
cost = 0
for right in range(len(nums)):
cost += nums[right]
while cost + k * (right - left + 1) > numOperations + nums[right] * (right - left + 1):
cost -= nums[left]
left += 1
max_freq = max(max_freq, right - left + 1)
return max_freq
# Test
test_nums = [1, 4, 5]
k = 1
numOperations = 2
print("Max Frequency:", maxFrequency(test_nums, k, numOperations))import java.util.Arrays;
public class Main {
public static int maxFrequency(int[] nums, int k, int numOperations) {
Arrays.sort(nums);
int left = 0, maxFreq = 0;
long cost = 0;
for (int right = 0; right < nums.length; right++) {
cost += nums[right];
while (cost + k * (right - left + 1) > numOperations + nums[right] * (right - left + 1)) {
cost -= nums[left];
left++;
}
maxFreq = Math.max(maxFreq, right - left + 1);
}
return maxFreq;
}
public static void main(String[] args) {
int[] nums = {1, 4, 5};
int k = 1, numOperations = 2;
System.out.println("Max Frequency: " + maxFrequency(nums, k, numOperations));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxFrequency(vector<int>& nums, int k, int numOperations) {
sort(nums.begin(), nums.end());
int left = 0, right;
long cost = 0;
int max_freq = 0;
for (right = 0; right < nums.size(); ++right) {
cost += nums[right];
while (cost + k * (right - left + 1) > numOperations + nums[right] * (right - left + 1)) {
cost -= nums[left];
++left;
}
max_freq = max(max_freq, right - left + 1);
}
return max_freq;
}
int main() {
vector<int> nums = {1, 4, 5};
int k = 1, numOperations = 2;
cout << "Max Frequency: " << maxFrequency(nums, k, numOperations) << endl;
return 0;
}function maxFrequency(nums, k, numOperations) {
nums.sort((a, b) => a - b);
let left = 0, maxFreq = 0;
let cost = 0;
for (let right = 0; right < nums.length; right++) {
cost += nums[right];
while (cost + k * (right - left + 1) > numOperations + nums[right] * (right - left + 1)) {
cost -= nums[left];
left++;
}
maxFreq = Math.max(maxFreq, right - left + 1);
}
return maxFreq;
}
// Test
const nums = [1, 4, 5];
const k = 1;
const numOperations = 2;
console.log("Max Frequency:", 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);
int left = 0, right;
long cost = 0;
int max_freq = 0;
for (right = 0; right < numsSize; ++right) {
cost += nums[right];
while (cost + k * (right - left + 1) > numOperations + nums[right] * (right - left + 1)) {
cost -= nums[left];
++left;
}
max_freq = max_freq > (right - left + 1) ? max_freq : (right - left + 1);
}
return max_freq;
}
int main() {
int nums[] = {1, 4, 5};
int k = 1, numOperations = 2;
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("Max Frequency: %d\n", maxFrequency(nums, numsSize, k, numOperations));
return 0;
}using System;
public class Solution {
public int MaxFrequency(int[] nums, int k, int numOperations) {
Array.Sort(nums);
int left = 0, maxFreq = 0;
long cost = 0;
for (int right = 0; right < nums.Length; right++) {
cost += nums[right];
while (cost + k * (right - left + 1) > numOperations + nums[right] * (right - left + 1)) {
cost -= nums[left];
left++;
}
maxFreq = Math.Max(maxFreq, right - left + 1);
}
return maxFreq;
}
public static void Main(string[] args) {
int[] nums = {1, 4, 5};
int k = 1, numOperations = 2;
Solution sol = new Solution();
Console.WriteLine("Max Frequency: " + sol.MaxFrequency(nums, k, numOperations));
}
}Sorts the array and uses two pointers to define a sliding window. Manages the addition of elements using a calculative cost mechanism, achieving maximum frequency with available operations.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) as no extra space usage is needed.
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.
def canFreqAchieve(nums, k, mid, numOperations, prefixSum):
for i in range(len(nums) - mid + 1):
j = i + mid - 1
totalOpsNeeded = nums[j] * mid - (prefixSum[j + 1] - prefixSum[i])
if totalOpsNeeded <= numOperations:
return True
return False
def maxFrequency(nums, k, numOperations):
nums.sort()
prefixSum = [0] * (len(nums) + 1)
for i in range(len(nums)):
prefixSum[i + 1] = prefixSum[i] + nums[i]
left, right, result = 1, len(nums), 1
while left <= right:
mid = left + (right - left) // 2
if canFreqAchieve(nums, k, mid, numOperations, prefixSum):
result = mid
left = mid + 1
else:
right = mid - 1
return result
# Test
test_nums = [1, 4, 5]
k = 1
numOperations = 2
print("Max Frequency:", maxFrequency(test_nums, k, numOperations))import java.util.Arrays;
public class Main {
public static boolean canFreqAchieve(int[] nums, int k, int mid, int numOperations, long[] prefixSum) {
for (int i = 0; i <= nums.length - mid; i++) {
int j = i + mid - 1;
long totalOpsNeeded = (long)nums[j] * mid - (prefixSum[j + 1] - prefixSum[i]);
if (totalOpsNeeded <= numOperations) return true;
}
return false;
}
public static int maxFrequency(int[] nums, int k, int numOperations) {
Arrays.sort(nums);
long[] prefixSum = new long[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int left = 1, right = nums.length, result = 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canFreqAchieve(nums, k, mid, numOperations, prefixSum)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 4, 5};
int k = 1, numOperations = 2;
System.out.println("Max Frequency: " + maxFrequency(nums, k, numOperations));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool canFreqAchieve(vector<int>& nums, int k, int mid, int numOperations, vector<long>& prefixSum) {
for (int i = 0; i <= nums.size() - mid; i++) {
int j = i + mid - 1;
long totalOpsNeeded = static_cast<long>(nums[j]) * mid - (prefixSum[j + 1] - prefixSum[i]);
if (totalOpsNeeded <= numOperations) return true;
}
return false;
}
int maxFrequency(vector<int>& nums, int k, int numOperations) {
sort(nums.begin(), nums.end());
vector<long> prefixSum(nums.size() + 1);
for (int i = 0; i < nums.size(); i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int left = 1, right = nums.size(), result = 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canFreqAchieve(nums, k, mid, numOperations, prefixSum)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
int main() {
vector<int> nums = {1, 4, 5};
int k = 1, numOperations = 2;
cout << "Max Frequency: " << maxFrequency(nums, k, numOperations) << endl;
return 0;
}function canFreqAchieve(nums, k, mid, numOperations, prefixSum) {
for (let i = 0; i <= nums.length - mid; i++) {
let j = i + mid - 1;
let totalOpsNeeded = BigInt(nums[j]) * BigInt(mid) - (prefixSum[j + 1] - prefixSum[i]);
if (totalOpsNeeded <= numOperations) {
return true;
}
}
return false;
}
function maxFrequency(nums, k, numOperations) {
nums.sort((a, b) => a - b);
let prefixSum = new Array(nums.length + 1).fill(0n);
for (let i = 0; i < nums.length; i++) {
prefixSum[i + 1] = prefixSum[i] + BigInt(nums[i]);
}
let left = 1;
let right = nums.length;
let result = 1;
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (canFreqAchieve(nums, k, mid, numOperations, prefixSum)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
// Test
const nums = [1, 4, 5];
const k = 1;
const numOperations = 2;
console.log("Max Frequency:", maxFrequency(nums, k, numOperations));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int canFreqAchieve(int *nums, int numsSize, int k, int mid, int numOperations, long *prefixSum) {
for (int i = 0; i <= numsSize - mid; i++) {
int j = i + mid - 1;
long totalOpsNeeded = (long)nums[j] * mid - (prefixSum[j + 1] - prefixSum[i]);
if (totalOpsNeeded <= (long)numOperations) return 1;
}
return 0;
}
int maxFrequency(int *nums, int numsSize, int k, int numOperations) {
qsort(nums, numsSize, sizeof(int), compare);
long prefixSum[numsSize + 1];
prefixSum[0] = 0;
for (int i = 0; i < numsSize; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int left = 1, right = numsSize;
int result = 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canFreqAchieve(nums, numsSize, k, mid, numOperations, prefixSum)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
int main() {
int nums[] = {1, 4, 5};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int k = 1, numOperations = 2;
printf("Max Frequency: %d\n", maxFrequency(nums, numsSize, k, numOperations));
return 0;
}using System;
public class Solution {
public bool CanFreqAchieve(int[] nums, int k, int mid, int numOperations, long[] prefixSum) {
for (int i = 0; i <= nums.Length - mid; i++) {
int j = i + mid - 1;
long totalOpsNeeded = (long)nums[j] * mid - (prefixSum[j + 1] - prefixSum[i]);
if (totalOpsNeeded <= numOperations) return true;
}
return false;
}
public int MaxFrequency(int[] nums, int k, int numOperations) {
Array.Sort(nums);
long[] prefixSum = new long[nums.Length + 1];
for (int i = 0; i < nums.Length; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int left = 1, right = nums.Length, result = 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (CanFreqAchieve(nums, k, mid, numOperations, prefixSum)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
public static void Main(string[] args) {
int[] nums = {1, 4, 5};
int k = 1, numOperations = 2;
Solution sol = new Solution();
Console.WriteLine("Max Frequency: " + sol.MaxFrequency(nums, k, numOperations));
}
}Augments prefix sum structure for verifying maximum achievable frequency post operations, with binary search driving the process. This strategy validates feasible operations to maximize singularity across elements.
Time Complexity: O(n log m) due to median-focused searching with prefix audition; Space Complexity: O(n) from prefix sum necessity.
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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sliding Window Technique | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) as no extra space usage is needed. |
| Approach 2: Binary Search with Prefix Sum | Time Complexity: O(n log m) due to median-focused searching with prefix audition; Space Complexity: O(n) from prefix sum necessity. |
| Difference Array | – |
Complexity analysis
| 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 |
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.