Maximum Frequency of an Element After Performing Operations I

Maximum Frequency of an Element After Performing Operations I - Problem

Array Binary Search Sliding Window Sorting Prefix Sum Medium

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.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: We can change nums[0] to 2 (add 1) and nums[1] to 2 (subtract 2). However, we can only do 2 operations, so we can change nums[0] to 2 and keep nums[1] as 4. But better: change nums[0] from 1 to 4 (add 3, but this exceeds k). Actually, change nums[0] from 1 to 2 and nums[1] from 4 to 2, but nums[1] needs to change by 2 which exceeds k=1. Best solution: target value 4, change nums[0] from 1 to 4 (not possible with k=1). Target value 5: change nums[1] from 4 to 5 and keep nums[2] as 5, giving frequency 2.

Example 2 — All Same Target

$ Input: nums = [2,2,2], k = 2, numOperations = 2

› Output: 3

💡 Note: All elements are already the same value 2. We don't need any operations, but we can use up to 2 operations on different indices. Since all 3 elements can have the same value without any operations, the maximum frequency is 3.

Example 3 — Limited Operations

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

› Output: 4

💡 Note: All elements are already 1. Even though we can only perform 1 operation, all 4 elements already have the same value, so the maximum frequency is 4.

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 nums=[1,4,5], k=1, numOperations=2

Process

Try different target values and count reachable elements

Output

Maximum frequency achievable is 2

Key Takeaway

🎯 Key Insight: Try each array element and its k-shifted values as potential targets to find maximum achievable frequency

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is that the optimal target value must be reachable by at least one element in the array. We can try each element and its k-shifted values as potential targets, then count how many elements can reach each target within the operation limit. The optimized approach sorts the array first and intelligently selects target candidates. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Possible Targets	O(n² × k)	O(n × k)	Try every possible target value and count how many elements can be adjusted to reach it
Binary Search on Answer	O(n² × k × log n)	O(n × k)	Binary search on the maximum possible frequency, checking if it's achievable
Optimized with Sorting and Sliding Window	O(n² + n log n)	O(1)	Sort elements first, then use sliding window to efficiently find maximum frequency

Brute Force - Try All Possible Targets — Algorithm Steps

Generate all possible target values each element can reach
For each target, count how many elements can reach it within numOperations
Return the maximum count found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Targets

Create all possible values each element can reach

Count Reachable

For each target, count elements that can reach it

Find Maximum

Return the highest count found

Code -

solution.c — C

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

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

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

int solution(int* nums, int n, int k, int numOperations) {
    // Find range of possible values
    int minVal = INT_MAX, maxVal = INT_MIN;
    for (int i = 0; i < n; i++) {
        minVal = nums[i] < minVal ? nums[i] : minVal;
        maxVal = nums[i] > maxVal ? nums[i] : maxVal;
    }
    
    int maxFreq = 0;
    // Try all possible target values in the range
    for (int target = minVal - k; target <= maxVal + k; target++) {
        int count = 0;
        int operationsUsed = 0;
        
        for (int i = 0; i < n; i++) {
            if (operationsUsed >= numOperations) break;
            // Check if this number can reach the target
            if (abs_val(nums[i] - target) <= k) {
                count++;
                operationsUsed++;
            }
        }
        
        maxFreq = max(maxFreq, count);
    }
    
    return maxFreq;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n² × k)

For each of O(n×k) possible targets, we check all n elements

⚠ Quadratic Growth

Space Complexity

O(n × k)

Store all possible target values in a set

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

324 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 Possible Targets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler