Maximum Equal Frequency - Practice Coding Problems

Maximum Equal Frequency - Problem

Given an array nums of positive integers, return the longest possible length of an array prefix of nums, such that it is possible to remove exactly one element from this prefix so that every number that has appeared in it will have the same number of occurrences.

If after removing one element there are no remaining elements, it's still considered that every appeared number has the same number of occurrences (0).

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,2,1,1,5,3,3,5]

› Output: 7

💡 Note: For prefix [2,2,1,1,5,3,3] of length 7, we can remove one occurrence of element 5, leaving frequencies: 2 appears 2 times, 1 appears 2 times, 3 appears 2 times - all equal

Example 2 — All Same Elements

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

› Output: 4

💡 Note: All elements are the same, so we can remove any one element and all remaining elements have the same frequency (3)

Example 3 — Remove to Empty

$ Input: nums = [1]

› Output: 1

💡 Note: Single element array - removing it leaves empty array where all elements have same frequency (0)

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of positive integers with varying frequencies

Check Prefixes

For each prefix, determine if removing one element equalizes frequencies

Find Maximum

Return the length of the longest valid prefix

Key Takeaway

🎯 Key Insight: Identify mathematical patterns where removing one element equalizes all frequencies

Asked in

G Google 25 f Facebook 18

The key insight is to recognize valid frequency patterns mathematically rather than trying all removals. We track element frequencies and frequency counts, then check if the current state matches patterns where removing one element makes all frequencies equal. Best approach uses optimized frequency tracking in O(n) time.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Frequency Tracking	O(n)	O(n)	Track frequency patterns and identify valid removal conditions mathematically
Brute Force - Try All Prefixes	O(n³)	O(n)	For each prefix, try removing each element and check if frequencies become equal

Optimized Frequency Tracking — Algorithm Steps

Maintain frequency map and frequency count map
For each prefix, check if it matches valid patterns
Valid patterns: all same frequency, all same except one extra, all frequency 1 except one, etc.
Return maximum valid prefix length

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Frequencies

Maintain maps for element frequencies and frequency counts

Check Patterns

For each prefix, check if it matches valid removal patterns

Valid Conditions

All same frequency, or specific mathematical patterns

Code -

solution.c — C

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

#define MAX_N 100000
#define MAX_VAL 100000

int isValid(int* count, int maxFreq, int length) {
    if (length == 1) return 1;
    
    int frequencies[1000];
    int freqCount = 0;
    
    for (int f = 1; f <= maxFreq; f++) {
        if (count[f] > 0) {
            frequencies[freqCount++] = f;
        }
    }
    
    if (freqCount == 1) {
        int f = frequencies[0];
        return f == 1 || count[f] == 1;
    }
    
    if (freqCount == 2) {
        int f1 = frequencies[0], f2 = frequencies[1];
        if (f1 > f2) {
            int temp = f1; f1 = f2; f2 = temp;
        }
        int c1 = count[f1], c2 = count[f2];
        
        if (f1 == 1 && c1 == 1) return 1;
        if (f2 == f1 + 1 && c2 == 1) return 1;
        if (f1 == 1 && f2 * c2 == length - 1) return 1;
    }
    
    return 0;
}

int solution(int* nums, int n) {
    int freq[MAX_VAL + 1] = {0};
    int count[MAX_N + 1] = {0}; // count[f] = how many numbers appear f times
    int maxLen = 0;
    int maxFreq = 0;
    
    for (int i = 0; i < n; i++) {
        int num = nums[i];
        
        // Update frequency maps
        if (freq[num] > 0) {
            count[freq[num]]--;
        }
        
        freq[num]++;
        count[freq[num]]++;
        if (freq[num] > maxFreq) maxFreq = freq[num];
        
        // Check if current prefix is valid
        if (isValid(count, maxFreq, i + 1)) {
            maxLen = i + 1;
        }
    }
    
    return maxLen;
}

int main() {
    char line[1000000];
    fgets(line, sizeof(line), stdin);
    
    int nums[MAX_N];
    int n = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, constant time checks for each position

✓ Linear Growth

Space Complexity

O(n)

Hash maps to store frequencies and frequency counts

⚡ Linearithmic Space

12.3K Views

Medium Frequency

~35 min Avg. Time

456 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

Optimized Frequency Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler