Apply Operations to Maximize Frequency Score

Apply Operations to Maximize Frequency Score - Problem

Array Binary Search Sliding Window Sorting Prefix Sum Hard

You are given a 0-indexed integer array nums and an integer k.

You can perform the following operation on the array at most k times:

Choose any index i from the array and increase or decrease nums[i] by 1.

The score of the final array is the frequency of the most frequent element in the array.

Return the maximum score you can achieve.

The frequency of an element is the number of occurrences of that element in the array.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: We can make [1,2,6,1] → [2,2,2,1] using 3 operations: change first 1→2 (1 op), change 6→2 (4 ops), but that exceeds k=3. Better: make [1,1,2] all equal to 2 with cost (2-1)+(2-1)+(2-2)=2≤3, giving frequency 3.

Example 2 — All Elements Same

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

› Output: 1

💡 Note: To make any 2 elements equal: min cost is |3-6|=3 or |3-9|=6 or |6-9|=3, all > k=2. So we can only achieve frequency 1.

Example 3 — Large Budget

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

› Output: 4

💡 Note: We can make all elements equal to 2: change two 1s to 2s costs 2 operations total. All 4 elements become 2, so frequency = 4.

Constraints

1 ≤ nums.length ≤ 5 × 10⁴
1 ≤ nums[i] ≤ 10⁹
0 ≤ k ≤ 2 × 10¹⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,6,1] with k=3 operations

Process

Sort and find optimal group of elements to unify

Output

Maximum frequency of 3 by making [1,1,2] all equal to 2

Key Takeaway

🎯 Key Insight: Sort first, then sliding window finds the largest group of elements that can be unified within the operation budget

Asked in

G Google 12 a Amazon 8 M Meta 6 M Microsoft 5

The key insight is to sort the array first, then use sliding window technique to efficiently find the maximum frequency achievable. The optimal approach uses binary search on the answer with O(n log n) time complexity, or direct sliding window with prefix sum optimization.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Targets	O(n³)	O(n)	Try every possible target value and calculate operations needed
Binary Search on Answer + Sliding Window	O(n log n)	O(1)	Binary search on frequency with sliding window to check feasibility
Optimized Sliding Window with Prefix Sum	O(n log n)	O(n)	Sort array and use sliding window with prefix sum for O(n log n) solution

Brute Force - Try All Targets — Algorithm Steps

Try each unique value as target
For each target, greedily convert closest elements
Track maximum frequency achieved

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Target

Pick a unique value as target

Calculate Costs

Find cost to convert each element

Greedy Selection

Take cheapest conversions within budget k

Code -

solution.c — C

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

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

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int solution(int* nums, int numsSize, int k) {
    int maxFreq = 0;
    
    // Try each element as target
    for (int i = 0; i < numsSize; i++) {
        int target = nums[i];
        
        // Calculate cost to convert each element to target
        int* costs = (int*)malloc(numsSize * sizeof(int));
        for (int j = 0; j < numsSize; j++) {
            costs[j] = abs_val(nums[j] - target);
        }
        
        // Sort by cost and greedily take cheapest conversions
        qsort(costs, numsSize, sizeof(int), compare);
        int totalCost = 0;
        int freq = 0;
        
        for (int j = 0; j < numsSize; j++) {
            if (totalCost + costs[j] <= k) {
                totalCost += costs[j];
                freq++;
            } else {
                break;
            }
        }
        
        if (freq > maxFreq) {
            maxFreq = freq;
        }
        
        free(costs);
    }
    
    return maxFreq;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int numsSize = 0;
    char* ptr = line + 1; // Skip '['
    while (*ptr != ']') {
        if (*ptr == ',' || *ptr == ' ') {
            ptr++;
            continue;
        }
        nums[numsSize++] = strtol(ptr, &ptr, 10);
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of n possible targets, we check all n elements and sort them by distance

⚠ Quadratic Growth

Space Complexity

O(n)

Extra array to store elements and their distances to target

⚡ Linearithmic Space

8.5K 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

Brute Force - Try All Targets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler