#1224

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximum Equal Frequency

Find the longest prefix of an array where removing one element makes all numbers appear equally, using efficient hash tracking.

array hash table

Problem Statement

Given an array nums of positive integers, find the length of the longest prefix where it is possible to remove exactly one element such that all remaining numbers occur the same number of times. The solution should focus on efficient scanning of the array with hash maps to track occurrences.

If removing one element leaves an empty array, it is considered valid as every appeared number then has zero occurrences. For example, given nums = [2,2,1,1,5,3,3,5], removing nums[4] = 5 from the prefix of length 7 produces [2,2,1,1,3,3] where each number appears twice.

Examples

Example 1

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

Output: 7

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 details omitted.

Constraints

2 <= nums.length <= 105
1 <= nums[i] <= 105

Solution Approach

Maintain Frequency Maps

Use a hash map to track the count of each number and another map to track the number of times each frequency occurs. This allows quick validation of the prefix at each index to see if removing one element would equalize frequencies.

Check Valid Prefix at Each Step

After updating counts for each number, evaluate if the current prefix can be balanced by removing one element. Key checks include whether one frequency is 1 or whether one frequency exceeds others by exactly 1, which matches the problem's core failure modes.

Update Maximum Prefix Length

Keep track of the maximum prefix length satisfying the condition dynamically as you iterate. This ensures the final result reflects the longest prefix without re-scanning the array, leveraging the hash-based counts for constant-time checks.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Array or Hash Table

We use $cnt$ to record the number of times each element $v$ appears in $nums$, and $ccnt$ to record the number of times each count appears. The maximum number of times an element appears is represented by $mx$.

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:
        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

Continue Practicing

#1218 longest arithmetic subsequence of given difference #1207 unique number of occurrences #1202 smallest string with swaps