HardNo. 1224
Maximum Equal Frequency — LeetCode 1224 Python Solution
- Pattern
- Hash Map
- Topics
- Array, Hash Table
- Reading time
- 3 min
- Source
- leetcode.com
The 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).
Example
- 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.
Python solution
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 ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1224. Maximum Equal Frequency is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1218 | Longest Arithmetic Subsequence of Given Difference | Medium |
| 0001 | Two Sum | Easy |
| 0036 | Valid Sudoku | Medium |
| 0037 | Sudoku Solver | Hard |
| 0041 | First Missing Positive | Hard |
| 0049 | Group Anagrams | Medium |
Frequently asked questions
- How hard is LeetCode 1224. Maximum Equal Frequency?
LeetCode 1224. Maximum Equal Frequency is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1224. Maximum Equal Frequency?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1224. Maximum Equal Frequency?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1224. Maximum Equal Frequency cover?
LeetCode 1224. Maximum Equal Frequency is tagged Array and Hash Table on LeetCode.