What is the key insight behind Maximum Equal Frequency?

The main insight is tracking number counts and frequency of frequencies dynamically to check if removing one element equalizes all counts.

Why do we need two hash maps in this problem?

One map counts occurrences of each number and the second counts how many numbers have each frequency, enabling constant-time prefix validation.

Can the solution handle arrays where all numbers are identical?

Yes, in this case, the prefix is the full array and removing any one element still maintains equal frequency, matching the problem pattern.

How does array scanning plus hash lookup pattern help here?

It allows incremental updates of counts and immediate checks for valid prefixes without rescanning, directly optimizing for Maximum Equal Frequency scenarios.

What edge cases should I watch for?

Single-element prefixes, prefixes where only one number occurs once, and cases where one frequency exceeds others by 1 are critical to handle.

#1224

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

最大相等频率

给你一个正整数数组 nums ，请你帮忙从该数组中找出能满足下面要求的最长前缀，并返回该前缀的长度：从前缀中恰好删除一个元素后，剩下每个数字的出现次数都相同。如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。示例 1：输入： nums = […

数组哈希表

题目描述

给你一个正整数数组 nums，请你帮忙从该数组中找出能满足下面要求的最长前缀，并返回该前缀的长度：

从前缀中 恰好删除一个 元素后，剩下每个数字的出现次数都相同。

如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。

示例 1：

输入：nums = [2,2,1,1,5,3,3,5]
输出：7
解释：对于长度为 7 的子数组 [2,2,1,1,5,3,3]，如果我们从中删去 nums[4] = 5，就可以得到 [2,2,1,1,3,3]，里面每个数字都出现了两次。

示例 2：

输入：nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
输出：13

提示：

2 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：数组或哈希表

我们用 $cnt$ 记录 $nums$ 中每个元素 $v$ 出现的次数，而 $ccnt$ 记录每个次数出现的次数，元素出现的最大次数用 $mx$ 表示。

遍历 $nums$ ：

若最大次数 $mx=1$ ，说明当前前缀中每个数字均出现 $1$ 次，删除任意一个后，都满足剩余数字次数相同；
若所有数字出现的次数均为 $mx$ 和 $mx-1$ ，并且只有一个数字的出现次数为 $mx$ ，那么我们删除出现 $mx$ 次数的一个数字，剩余数字次数均为 $mx-1$ ，满足条件；
若除了一个数字，其它所有数字出现次数均为 $mx$ 次，那么我们删除出现一次的数字，剩余数字次数均为 $mx$ ，满足条件。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 表示 $nums$ 数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        cnt = Counter()
        ccnt = Counter()
        ans = mx = 0
        for i, v in enumerate(nums, 1):
            if v in cnt:
                ccnt[cnt[v]] -= 1
            cnt[v] += 1
            mx = max(mx, cnt[v])
            ccnt[cnt[v]] += 1
            if mx == 1:
                ans = i
            elif ccnt[mx] * mx + ccnt[mx - 1] * (mx - 1) == i and ccnt[mx] == 1:
                ans = i
            elif ccnt[mx] * mx + 1 == i and ccnt[1] == 1:
                ans = i
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) since each number is processed once with constant-time hash map updates and checks. Space complexity is O(n) in the worst case due to storing counts and frequency maps.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates should recognize the pattern of array scanning combined with hash maps for frequency tracking.
question_mark
Expect hints about handling one outlier frequency to validate prefixes efficiently.
question_mark
Watch for solutions that attempt to recalc frequencies repeatedly instead of maintaining dynamic counts.

warning

常见陷阱

外企场景

error
Forgetting that a prefix of length 1 is always valid even after removing the element.
error
Failing to handle the case where the maximum frequency occurs for multiple numbers.
error
Over-scanning the array or recalculating counts instead of using hash maps dynamically.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Determine the maximum prefix where removing up to two elements allows equal frequencies.
arrow_right_alt
Return the prefix length where exactly k distinct numbers must end with the same frequency after one removal.
arrow_right_alt
Compute longest prefix where the difference between max and min frequency is at most 1 without any removal.

help

常见问题

外企场景

继续练习

#1218 最长定差子序列 #1207 独一无二的出现次数 #1202 交换字符串中的元素