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

Examples

Example 1

1
2
3

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

1
2

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

Constraints

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

Solution

Method 1 – Hash Map and Frequency Counting

Intuition

We want to find the longest prefix such that, after removing one element, all numbers have the same frequency. By tracking the count of each number and the count of each frequency, we can check at each step if the prefix is valid.

Approach

  1. Use a hash map to count occurrences of each number (cnt).
  2. Use another hash map to count how many numbers have each frequency (freq).
  3. For each index in nums, update cnt and freq for the current number.
  4. At each step, check if the prefix can be made valid by removing one element:
    • All numbers have frequency 1.
    • Only one number has frequency 1, and the rest have the same frequency.
    • Only one number has a frequency greater by 1 than the rest, and it occurs once.
  5. Keep track of the maximum valid prefix length.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        unordered_map<int, int> cnt, freq;
        int ans = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            int x = nums[i];
            if (cnt[x]) freq[cnt[x]]--;
            cnt[x]++;
            freq[cnt[x]]++;
            int f1 = freq[1], f2 = freq[cnt[x]], maxf = cnt[x];
            int total = i+1;
            if (maxf == 1 ||
                (freq[maxf]*maxf + freq[maxf-1]*(maxf-1) == total && freq[maxf] == 1) ||
                (freq[1] == 1 && freq[maxf]*maxf + freq[maxf-1]*(maxf-1) == total-1))
                ans = total;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func maxEqualFreq(nums []int) int {
    cnt := map[int]int{}
    freq := map[int]int{}
    ans := 0
    for i, x := range nums {
        if cnt[x] > 0 {
            freq[cnt[x]]--
        }
        cnt[x]++
        freq[cnt[x]]++
        maxf := cnt[x]
        total := i+1
        if maxf == 1 ||
            (freq[maxf]*maxf+freq[maxf-1]*(maxf-1) == total && freq[maxf] == 1) ||
            (freq[1] == 1 && freq[maxf]*maxf+freq[maxf-1]*(maxf-1) == total-1) {
            ans = total
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int maxEqualFreq(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>(), freq = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            if (cnt.getOrDefault(x, 0) > 0) freq.put(cnt.get(x), freq.get(cnt.get(x))-1);
            cnt.put(x, cnt.getOrDefault(x, 0)+1);
            freq.put(cnt.get(x), freq.getOrDefault(cnt.get(x), 0)+1);
            int maxf = cnt.get(x), total = i+1;
            if (maxf == 1 ||
                (freq.getOrDefault(maxf,0)*maxf + freq.getOrDefault(maxf-1,0)*(maxf-1) == total && freq.getOrDefault(maxf,0) == 1) ||
                (freq.getOrDefault(1,0) == 1 && freq.getOrDefault(maxf,0)*maxf + freq.getOrDefault(maxf-1,0)*(maxf-1) == total-1))
                ans = total;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun maxEqualFreq(nums: IntArray): Int {
        val cnt = mutableMapOf<Int, Int>()
        val freq = mutableMapOf<Int, Int>()
        var ans = 0
        for ((i, x) in nums.withIndex()) {
            if (cnt[x] != null && cnt[x]!! > 0) freq[cnt[x]!!] = freq.getOrDefault(cnt[x]!!, 0) - 1
            cnt[x] = cnt.getOrDefault(x, 0) + 1
            freq[cnt[x]!!] = freq.getOrDefault(cnt[x]!!, 0) + 1
            val maxf = cnt[x]!!
            val total = i+1
            if (maxf == 1 ||
                (freq.getOrDefault(maxf,0)*maxf + freq.getOrDefault(maxf-1,0)*(maxf-1) == total && freq.getOrDefault(maxf,0) == 1) ||
                (freq.getOrDefault(1,0) == 1 && freq.getOrDefault(maxf,0)*maxf + freq.getOrDefault(maxf-1,0)*(maxf-1) == total-1))
                ans = total
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def maxEqualFreq(self, nums: list[int]) -> int:
        from collections import defaultdict
        cnt = defaultdict(int)
        freq = defaultdict(int)
        ans = 0
        for i, x in enumerate(nums):
            if cnt[x]:
                freq[cnt[x]] -= 1
            cnt[x] += 1
            freq[cnt[x]] += 1
            maxf = cnt[x]
            total = i+1
            if maxf == 1 or \
                (freq[maxf]*maxf + freq[maxf-1]*(maxf-1) == total and freq[maxf] == 1) or \
                (freq[1] == 1 and freq[maxf]*maxf + freq[maxf-1]*(maxf-1) == total-1):
                ans = total
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn max_equal_freq(nums: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        let mut cnt = HashMap::new();
        let mut freq = HashMap::new();
        let mut ans = 0;
        for (i, &x) in nums.iter().enumerate() {
            if let Some(&c) = cnt.get(&x) {
                *freq.entry(c).or_insert(0) -= 1;
            }
            let c = cnt.entry(x).or_insert(0);
            *c += 1;
            *freq.entry(*c).or_insert(0) += 1;
            let maxf = *c;
            let total = i+1;
            if maxf == 1 ||
                (freq.get(&maxf).unwrap_or(&0)*maxf as i32 + freq.get(&(maxf-1)).unwrap_or(&0)*(maxf-1) as i32 == total as i32 && *freq.get(&maxf).unwrap_or(&0) == 1) ||
                (*freq.get(&1).unwrap_or(&0) == 1 && freq.get(&maxf).unwrap_or(&0)*maxf as i32 + freq.get(&(maxf-1)).unwrap_or(&0)*(maxf-1) as i32 == total as i32 - 1) {
                ans = total as i32;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    maxEqualFreq(nums: number[]): number {
        const cnt = new Map<number, number>(), freq = new Map<number, number>();
        let ans = 0;
        for (let i = 0; i < nums.length; i++) {
            const x = nums[i];
            if (cnt.has(x) && cnt.get(x)! > 0) freq.set(cnt.get(x)!, (freq.get(cnt.get(x)!) ?? 0) - 1);
            cnt.set(x, (cnt.get(x) ?? 0) + 1);
            freq.set(cnt.get(x)!, (freq.get(cnt.get(x)!) ?? 0) + 1);
            const maxf = cnt.get(x)!;
            const total = i+1;
            if (maxf == 1 ||
                ((freq.get(maxf) ?? 0)*maxf + (freq.get(maxf-1) ?? 0)*(maxf-1) == total && (freq.get(maxf) ?? 0) == 1) ||
                ((freq.get(1) ?? 0) == 1 && (freq.get(maxf) ?? 0)*maxf + (freq.get(maxf-1) ?? 0)*(maxf-1) == total-1))
                ans = total;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array, as we process each element once.
  • 🧺 Space complexity: O(n), for the hash maps.