Code Implementation

from collections import Counter, defaultdict

class Solution:
    def maxEqualFreq(self, nums):
        count = Counter()
        freq = Counter()
        res = 0

        for i, num in enumerate(nums):
            if count[num]:
                freq[count[num]] -= 1
            count[num] += 1
            freq[count[num]] += 1

            maxf = max(count.values())
            n = i + 1

            # 1. All numbers appear once
            # 2. All but one number appear maxf, one appears once
            # 3. All but one number appear maxf-1, one appears maxf
            if maxf == 1 or \
                freq[maxf] * maxf + freq[maxf-1] * (maxf-1) == n and freq[maxf] == 1 or \
                freq[maxf] * maxf + 1 == n and freq[1] == 1:
                res = n
        return res
      

#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        unordered_map<int, int> count, freq;
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int num = nums[i];
            if (count[num])
                freq[count[num]]--;
            count[num]++;
            freq[count[num]]++;
            int maxf = 0;
            for (auto &p : count)
                maxf = max(maxf, p.second);
            int n = i + 1;

            if (maxf == 1 ||
                freq[maxf] * maxf + freq[maxf - 1] * (maxf - 1) == n && freq[maxf] == 1 ||
                freq[maxf] * maxf + 1 == n && freq[1] == 1) {
                res = n;
            }
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int maxEqualFreq(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        Map<Integer, Integer> freq = new HashMap<>();
        int res = 0;
        for (int i = 0; i < nums.length; ++i) {
            int num = nums[i];
            if (count.containsKey(num)) {
                freq.put(count.get(num), freq.get(count.get(num)) - 1);
            }
            count.put(num, count.getOrDefault(num, 0) + 1);
            freq.put(count.get(num), freq.getOrDefault(count.get(num), 0) + 1);

            int maxf = 0;
            for (int v : count.values())
                maxf = Math.max(maxf, v);
            int n = i + 1;

            if (maxf == 1 ||
                freq.getOrDefault(maxf, 0) * maxf + freq.getOrDefault(maxf - 1, 0) * (maxf - 1) == n && freq.getOrDefault(maxf, 0) == 1 ||
                freq.getOrDefault(maxf, 0) * maxf + 1 == n && freq.getOrDefault(1, 0) == 1) {
                res = n;
            }
        }
        return res;
    }
}
      

var maxEqualFreq = function(nums) {
    let count = new Map();
    let freq = new Map();
    let res = 0;
    for (let i = 0; i < nums.length; ++i) {
        let num = nums[i];
        if (count.has(num)) {
            freq.set(count.get(num), (freq.get(count.get(num)) || 0) - 1);
        }
        count.set(num, (count.get(num) || 0) + 1);
        freq.set(count.get(num), (freq.get(count.get(num)) || 0) + 1);

        let maxf = 0;
        for (let v of count.values()) {
            maxf = Math.max(maxf, v);
        }
        let n = i + 1;

        if (maxf === 1 ||
            (freq.get(maxf) * maxf + (freq.get(maxf - 1) || 0) * (maxf - 1) === n && freq.get(maxf) === 1) ||
            (freq.get(maxf) * maxf + 1 === n && freq.get(1) === 1)) {
            res = n;
        }
    }
    return res;
};
      

Problem Description

You are given an array of positive integers nums. Your task is to find the length of the longest prefix of nums such that, after removing at most one element from this prefix, every number in the prefix appears the same number of times.

• You can remove at most one element from the prefix.
• You must find the maximum length of such a prefix.
• The prefix must start from the first element and include contiguous elements.

Constraints:

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

Thought Process

At first glance, you might consider checking every possible prefix and, for each, removing every possible element to check if the remaining numbers all have the same frequency. However, this brute-force approach is too slow for large arrays.

To optimize, let's observe what it means for a prefix to be "almost" equal-frequency. If we can remove one element and all remaining elements have the same count, one of a few scenarios must be true:

• All elements appear exactly once (removal optional).
• All elements appear the same number of times, except one number that appears once more or once less.
• All but one element appear once, and one element appears more times.

• The count of each number seen so far.
• The frequency of those counts (i.e., how many numbers have count 1, 2, etc.).

Solution Approach

Let's break down the algorithm step by step:

1. Initialize two hash maps:
   • count: tracks how many times each number has appeared.
   • freq: tracks how many numbers have a given frequency.
2. Iterate through the array:
   • For each number, update its count in count.
   • Before updating, decrease the frequency of its old count in freq (if it had appeared before).
   • After updating, increase the frequency of its new count.
3. After each update, check if the current prefix can be made equal-frequency by removing at most one element.
   • Find the current maximum frequency maxf.
   • Check these possible cases:
     • All numbers appear once: maxf == 1.
     • All numbers but one have frequency maxf, and one has maxf-1 (and only one number with maxf): freq[maxf] * maxf + freq[maxf-1] * (maxf-1) == n and freq[maxf] == 1.
     • All numbers but one have frequency 1, and one has maxf: freq[maxf] * maxf + 1 == n and freq[1] == 1.
   • If any of these hold, update the result to the current prefix length.
4. Return the maximum valid prefix length found.

Using hash maps ensures all operations are efficient, even for large arrays.

Example Walkthrough

Let's take nums = [2,2,1,1,5,3,3,5].

• After processing the first 7 elements: [2,2,1,1,5,3,3]
  • Counts: 2 appears 2 times, 1 appears 2 times, 5 appears 1 time, 3 appears 2 times.
  • Frequency of counts: 2 appears 3 times, 1 appears 1 time.
  • Total elements: 7.
  • Check the conditions:
    • All appear once? No.
    • All but one have the same frequency, one appears once? 3*2 + 1*1 = 7 and freq[2]=3, freq[1]=1. Yes!
  • So, prefix length 7 is valid.
• Add the 8th element (5): [2,2,1,1,5,3,3,5]
  • Counts: 2:2, 1:2, 5:2, 3:2
  • Frequency: 2 appears 4 times
  • All appear twice? Yes. So, the entire array is valid.
• The answer is 8.

This step-by-step check ensures we only accept prefixes where, after at most one removal, all numbers have equal frequency.

Time and Space Complexity

• Brute-force approach:
  • For each prefix, try removing each element and check frequencies: O(N^2) time, which is too slow for large inputs.
• Optimized approach (using hash maps):
  • Each number is processed once, and all hash map operations are O(1) on average.
  • Finding the max frequency among counts is O(1) because at most two different frequencies exist at any time.
  • Overall time complexity: O(N)
  • Space complexity: O(N) for the counters (in worst case, all numbers are unique).

Summary

The key insight is that only a few special cases allow a prefix to be made equal-frequency by removing at most one element. By maintaining running counts and frequencies in hash maps, we can check these cases efficiently as we process the array. This approach ensures a linear-time solution, making it suitable for large inputs and leveraging the properties of prefix subarrays and frequency distributions.