Maximum Frequency of an Element After Performing Operations II

Maximum Frequency of an Element After Performing Operations II - Problem

Array Binary Search Sliding Window Sorting Prefix Sum Hard

You are given an integer array nums and two integers k and numOperations.

You must perform an operation exactly 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,4,6], k = 3, numOperations = 2

› Output: 3

💡 Note: Choose target value 4. Modify nums[0]: 2→4 and nums[2]: 6→4. Result: [4,4,4] with frequency 3.

Example 2 — Limited Operations

$ Input: nums = [1,4,5], k = 1, numOperations = 2

› Output: 3

💡 Note: Choose target value 4. Modify nums[0]: 1→4 and nums[2]: 5→4. Result: [4,4,4] with frequency 3.

Example 3 — No Operations Needed

$ Input: nums = [3,3,3], k = 1, numOperations = 1

› Output: 3

💡 Note: All elements are already equal to 3. No operations needed, frequency is already 3.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹
0 ≤ k ≤ 10⁹
0 ≤ numOperations ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array with k constraint and numOperations limit

Process

Choose target and apply operations optimally

Output

Maximum frequency achievable

Key Takeaway

🎯 Key Insight: Binary search the maximum frequency and greedily verify feasibility by assigning operations to closest elements

Asked in

G Google 15 f Meta 12 M Microsoft 8

The key insight is to realize that for any target value, we should greedily assign operations to elements that are closest to the target. The best approach uses binary search on the answer combined with greedy verification. For each candidate frequency, we test all possible target values and greedily assign operations to minimize modification costs. Time: O(n² log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(n² log n)	O(n)	Binary search the maximum frequency, then check if it's achievable
Brute Force - Try All Targets	O(n³ × 2^n)	O(n)	Try every possible target value and check maximum achievable frequency
Sliding Window with Sorting	O(n² log n)	O(n)	Sort array and use sliding window to find optimal target ranges

Binary Search on Answer — Algorithm Steps

Binary search on frequency from 1 to n
For each frequency, try all possible target values
Greedily assign operations to achieve the target frequency

Visualization

Tap to expand

Step-by-Step Walkthrough

Search Space

Binary search frequency from 1 to n

Check Feasibility

For each frequency, test if achievable with operations

Narrow Range

Update search bounds based on feasibility

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

int canAchieveFreq(int* nums, int numsSize, int k, int numOperations, int targetFreq) {
    // Try some target values
    int targets[1000];
    int targetCount = 0;
    
    for (int i = 0; i < numsSize && targetCount < 800; i++) {
        for (int delta = -k; delta <= k && targetCount < 800; delta++) {
            targets[targetCount++] = nums[i] + delta;
        }
    }
    
    for (int t = 0; t < targetCount; t++) {
        int target = targets[t];
        int equalCount = 0;
        int canModify[numsSize];
        int modifyCount = 0;
        
        for (int i = 0; i < numsSize; i++) {
            if (nums[i] == target) {
                equalCount++;
            } else if (abs(nums[i] - target) <= k) {
                canModify[modifyCount++] = abs(nums[i] - target);
            }
        }
        
        qsort(canModify, modifyCount, sizeof(int), compare);
        
        int need = max(0, targetFreq - equalCount);
        if (need <= modifyCount && need <= numOperations) {
            return 1;
        }
    }
    
    return 0;
}

int solution(int* nums, int numsSize, int k, int numOperations) {
    int left = 1, right = numsSize;
    int result = 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (canAchieveFreq(nums, numsSize, k, numOperations, mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL && numsSize < 1000) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int k, numOperations;
    scanf("%d", &k);
    scanf("%d", &numOperations);
    
    int result = solution(nums, numsSize, k, numOperations);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

Binary search O(log n) × checking O(n) targets × O(n) greedy assignment

⚠ Quadratic Growth

Space Complexity

O(n)

Storage for sorted distances and greedy assignment

⚡ Linearithmic Space

8.8K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler