Maximum Equal Frequency

Hard
1784.

Maximum Equal Frequency

Maximum Equal Frequency is a hard coding problem on arrays, hash table and counting, asked in Amazon interviews.

You are given an array nums of positive integers.

Return the length of the longest prefix of nums from which you can remove exactly one element so that every number still present in the prefix occurs the same number of times.

If removing that element leaves the prefix empty, it still counts: an empty selection has every (no) number occurring equally often.

Example 1

Input
nums = [4,4,7,7,9,6,6,9]
Output
7
Explanation
The prefix `[4,4,7,7,9,6,6]` drops its single 9 to leave 4, 7 and 6 twice each. The whole array cannot work: two 9s already give every value two copies, and any removal breaks that.

Example 2

Input
nums = [5,5,5,8,8,8,2]
Output
7
Explanation
Remove the 2: both 5 and 8 then occur three times.

Example 3

Input
nums = [1,2]
Output
2
Explanation
Remove either element; the one left occurs once.

Constraints

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxEqualFreq = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Equal Frequency — Solution in Python, Java & C++

Maximum Equal Frequency solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon.

Maximum Equal Frequency is a hard coding problem on arrays, hash table and counting, asked in Amazon interviews.

  • Difficulty: Hard
  • Topics: Arrays, Hash Table, Counting
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array nums of positive integers.

Return the length of the longest prefix of nums from which you can remove exactly one element so that every number still present in the prefix occurs the same number of times.

If removing that element leaves the prefix empty, it still counts: an empty selection has every (no) number occurring equally often.

Example 1

Input: nums = [4,4,7,7,9,6,6,9]
Output: 7
Explanation: The prefix `[4,4,7,7,9,6,6]` drops its single 9 to leave 4, 7 and 6 twice each. The whole array cannot work: two 9s already give every value two copies, and any removal breaks that.

Example 2

Input: nums = [5,5,5,8,8,8,2]
Output: 7
Explanation: Remove the 2: both 5 and 8 then occur three times.

Example 3

Input: nums = [1,2]
Output: 2
Explanation: Remove either element; the one left occurs once.

Constraints

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

Hints for Maximum Equal Frequency

  1. Hint 1

    Track, while scanning the prefix, how often each number occurs and how many numbers have each occurrence count.

  2. Hint 2

    With maxF the largest occurrence count, only three shapes allow a single removal to equalise everything.

  3. Hint 3

    The shapes: every count is 1; every number occurs maxF times except one number that occurs once; or one number occurs maxF times and every other number maxF - 1 times. Each can be checked in O(1) with the two tables.

How to solve Maximum Equal Frequency

Keep cnt[x] (occurrences of x) and freq[c] (how many numbers occur exactly c times) as the prefix grows. Whether a prefix of length L qualifies depends only on maxF and freq, through three O(1) tests.

Approach

  1. For each index i, move nums[i] from count c to c + 1: decrement freq[c], increment freq[c + 1], and update maxF.
  2. Let L = i + 1. The prefix qualifies if maxF == 1 (remove any element), or maxF * freq[maxF] == L - 1 (all numbers occur maxF times plus one stray element that occurs once — remove it), or (maxF - 1) * (freq[maxF - 1] + 1) == L - 1 (one number occurs maxF times and the rest maxF - 1 — remove one copy of it).
  3. Record the last qualifying L.

Why it works

Removing one element changes a single number's count by one. For the remaining counts to be equal, either the removed element was the only copy of its number (the others all share one count) or it reduced the unique maximum to match the rest. The two equations restate exactly those shapes as sums over freq: in each, the left side counts the elements that stay, so it must equal L - 1. All-ones is the degenerate case where any removal works.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Forgetting the single-distinct-number prefix ([7,7,7]): it is covered by the third test with freq[maxF - 1] = 0.
  • Checking only the full array: the answer is the longest qualifying prefix, so test every length.
  • Exactly one element must be removed — an array whose counts are already all equal (and not all 1) does not qualify as is.

Reference solution

Python

from typing import List

def maxEqualFreq(nums: List[int]) -> int:
    cnt = {}
    freq = [0] * (len(nums) + 2)
    max_f = 0
    ans = 0
    for i, x in enumerate(nums):
        c = cnt.get(x, 0)
        if c:
            freq[c] -= 1
        c += 1
        cnt[x] = c
        freq[c] += 1
        if c > max_f:
            max_f = c
        if (max_f == 1 or max_f * freq[max_f] == i
                or (max_f - 1) * (freq[max_f - 1] + 1) == i):
            ans = i + 1
    return ans

Java

public static int maxEqualFreq(int[] nums) {
    int n = nums.length;
    int[] cnt = new int[100001];
    int[] freq = new int[n + 2];
    int maxF = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        int c = cnt[nums[i]];
        if (c > 0) freq[c]--;
        c++;
        cnt[nums[i]] = c;
        freq[c]++;
        maxF = Math.max(maxF, c);
        if (maxF == 1 || maxF * freq[maxF] == i || (maxF - 1) * (freq[maxF - 1] + 1) == i) ans = i + 1;
    }
    return ans;
}

C++

int maxEqualFreq(vector<int>& nums) {
    int n = nums.size();
    unordered_map<int, int> cnt;
    vector<int> freq(n + 2, 0);
    int maxF = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        int& c = cnt[nums[i]];
        if (c > 0) freq[c]--;
        c++;
        freq[c]++;
        maxF = max(maxF, c);
        if (maxF == 1 || maxF * freq[maxF] == i || (maxF - 1) * (freq[maxF - 1] + 1) == i) ans = i + 1;
    }
    return ans;
}

JavaScript

var maxEqualFreq = function(nums) {
    var cnt = new Map();
    var freq = new Array(nums.length + 2).fill(0);
    var maxF = 0, ans = 0;
    for (var i = 0; i < nums.length; i++) {
        var c = cnt.get(nums[i]) || 0;
        if (c > 0) freq[c]--;
        c++;
        cnt.set(nums[i], c);
        freq[c]++;
        if (c > maxF) maxF = c;
        if (maxF === 1 || maxF * freq[maxF] === i || (maxF - 1) * (freq[maxF - 1] + 1) === i) ans = i + 1;
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets