Algorithm (Counter)

1. Let $A$ be the input array. We note that $A[1:m]$ is a valid prefix of $A$ if and only if it is of the following form:

   1. $[a,....,a]$
   2. $[a_{1},…,a_{n}]$ such that $a_{1}\neq a_{2}\neq…\neq a_{n}$
   3. $\mathcal{G}=[G_{1},G_{2},…,G_{l-1},G_{l}]$ where $G_{i}$ is the equivalent class fromed by the relationship $x\sim y\text{ iff }x=y$ and $\text{map}(\lambda x.\mathrm{size}(x),\mathcal{G})\in\{(k,…,k,1),(k,…,k,k+1)\}.$

2. These three conditions could be verified by two counters maps in a linear scan.

Code

class Solution {
 public:
  int maxEqualFreq(vector<int>& nums) {

    const auto solution = [&](int acc = INT_MIN) {      
      struct state_t {
        std::unordered_map<int, int> counter_of_counter;
        std::unordered_map<int, int> counter;       

        const state_t& update(int num)  {
          if (--counter_of_counter[counter[num]] <= 0)
            counter_of_counter.erase(counter[num]);
          ++counter_of_counter[++counter[num]];
          return *this;
        }
      };

      for (auto[i, state] = pair{0, state_t{}}; i < size(nums); ++i) {
        const auto &[counter_of_counter, counter] = state.update(nums[i]);
        if (size(counter_of_counter) == 1) {
          const auto [freq1, cnt1] = *begin(counter_of_counter);
          if (cnt1 == 1 or freq1 == 1)
            acc = std::max(acc, i + 1);
        }
        else if (size(counter_of_counter) == 2) {
          const auto [freq1, cnt1] = *begin(counter_of_counter);
          const auto [freq2, cnt2] = *(std::next(begin(counter_of_counter)));
          if ((freq1 == 1 and cnt1 == 1) or (freq2 == 1 and cnt2 == 1))
            acc = std::max(acc, i + 1);
          else if (freq1 + 1 == freq2 and cnt2 ==1)
            acc = std::max(acc, i + 1);
          else if (freq2 + 1 == freq1 and cnt1 ==1)
            acc = std::max(acc, i + 1);
        }
      }
      return acc;
    }();

    return solution;
  }
};