Frequency of the Most Frequent Element - Practice Coding Problems

Frequency of the Most Frequent Element - Problem

Array Binary Search Greedy Sliding Window Sorting Prefix Sum Medium

The frequency of an element is the number of times it occurs in an array.

You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most k operations.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: We can make all elements equal to 4 by incrementing 1 by 3 and 2 by 2, using 5 operations total. Final array: [4,4,4] with frequency 3.

Example 2 — Limited Operations

$ Input: nums = [1,4,8,13], k = 5

› Output: 2

💡 Note: We can make [1,4] both equal to 4 using 3 operations (1→4 needs 3 ops). Or make [4,8] both equal to 8 using 4 operations. Maximum frequency is 2.

Example 3 — Single Element

$ Input: nums = [3], k = 0

› Output: 1

💡 Note: With only one element and no operations allowed, the maximum frequency is 1.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,4] with k=5 operations available

Process

Choose target value and increment smaller elements

Output

Maximum achievable frequency is 3

Key Takeaway

🎯 Key Insight: Sort the array first, then use sliding window to find the longest subarray that can be made equal within k operations

Asked in

a Amazon 45 G Google 38 M Microsoft 32 🍎 Apple 25

The key insight is to sort the array first and use a sliding window approach. We always target the rightmost element in the current window as our goal value. The optimal approach uses sliding window with prefix sums for O(n log n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Targets	O(n³)	O(1)	Try every possible target value and calculate operations needed
Sort + Sliding Window	O(n² log n)	O(1)	Sort array first, then use sliding window to find longest achievable sequence
Optimized Sliding Window with Prefix Sum	O(n log n)	O(1)	Sort array and use sliding window with prefix sums for O(n log n) solution

Brute Force - Try All Targets — Algorithm Steps

Step 1: For each possible target value
Step 2: For each subarray, calculate operations needed
Step 3: Track maximum frequency achievable within k operations

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Target

Pick a target value to make elements equal

Test Subarrays

For each subarray, count operations needed

Track Maximum

Keep track of best frequency found

Code -

solution.c — C

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

int solution(int* nums, int numsSize, int k) {
    int maxFreq = 1;
    
    // Find max value
    int maxVal = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
        }
    }
    
    // Try all possible target values
    for (int target = 1; target <= maxVal + k; target++) {
        // Try all subarrays
        for (int i = 0; i < numsSize; i++) {
            int operations = 0;
            int freq = 0;
            for (int j = i; j < numsSize; j++) {
                if (nums[j] <= target) {
                    operations += target - nums[j];
                    if (operations <= k) {
                        freq++;
                        if (freq > maxFreq) {
                            maxFreq = freq;
                        }
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            }
        }
    }
    
    return maxFreq;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: target values × subarrays × elements in subarray

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

89.0K Views

High Frequency

~25 min Avg. Time

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