1224. Maximum Equal Frequency

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 ocurrences (0).

 

Example 1:

Input: nums = [2,2,1,1,5,3,3,5]
Output: 7
Explanation: For the subarray [2,2,1,1,5,3,3] of length 7, if we remove nums[4]=5, we will get [2,2,1,1,3,3], so that each number will appear exactly twice.

Example 2:

Input: nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
Output: 13

Example 3:

Input: nums = [1,1,1,2,2,2]
Output: 5

Example 4:

Input: nums = [10,2,8,9,3,8,1,5,2,3,7,6]
Output: 8

 

Constraints:

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

Rust Solution

struct Solution;
use std::collections::HashMap;

impl Solution {
    fn max_equal_freq(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut res = 0;
        let mut count: HashMap<i32, usize> = HashMap::new();
        let mut freq: HashMap<usize, usize> = HashMap::new();
        let mut max_freq = 0;
        for i in 0..n {
            let f = count.entry(nums[i]).or_default();
            if *f != 0 {
                *freq.entry(*f).or_default() -= 1;
            }
            *f += 1;
            *freq.entry(*f).or_default() += 1;
            max_freq = max_freq.max(*f);
            if max_freq == 1
                || *freq.entry(max_freq).or_default() * max_freq == i
                || (*freq.entry(max_freq - 1).or_default() + 1) * (max_freq - 1) == i
            {
                res = res.max(i + 1);
            }
        }
        res as i32
    }
}

#[test]
fn test() {
    let nums = vec![2, 2, 1, 1, 5, 3, 3, 5];
    let res = 7;
    assert_eq!(Solution::max_equal_freq(nums), res);
    let nums = vec![1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5];
    let res = 13;
    assert_eq!(Solution::max_equal_freq(nums), res);
    let nums = vec![1, 1, 1, 2, 2, 2];
    let res = 5;
    assert_eq!(Solution::max_equal_freq(nums), res);
}

Having problems with this solution? Click here to submit an issue on github.