1224. Maximum Equal Frequency
Problem Description
In this problem, we are given an array nums
consisting of positive integers. The goal is to find the length of the longest prefix (an initial segment of the array) with the property that if you remove exactly one element from it, all the remaining numbers in the prefix will have the same frequency of occurrence.
This means that in the longest prefix, for all the numbers that have appeared thus far, either all numbers appear the same number of times, or removing one instance of a number can achieve this state of equal frequency.
An important part of the description specifies that if we end up removing one element from the prefix, and there are no elements left, this also counts as having all numbers appearing with the same frequency (since they all appear zero times).
Intuition
To solve this problem, we need to keep track of two things at each step:
- The frequency of each number in the prefix (
cnt
). - The count of frequencies that we've seen (
ccnt
).
Using these two counters, we can determine at each step if the prefix can have equal frequency after removing a single element, and hence calculate the longest such prefix.
The thinking process is to iterate through the array, and at each step, update our two counters: one for the frequency of the current element (cnt[v]
) and another for the frequency of this frequency (ccnt[cnt[v]]
). While doing so, we maintain a variable mx
that stores the maximum frequency of any number in the prefix so far.
We consider three cases where the prefix could potentially have all numbers appearing the same number of times after removing one element:
- If the maximum frequency (
mx
) is 1, which means all elements are unique, any prefix is valid by removing any one of them. - If the highest frequency number (
mx
) appears exactly once (ccnt[mx] == 1
) and the rest of the numbers have one less frequency (mx - 1
), then by removing the single occurrence of the highest frequency number, all numbers would have the same frequency. - Likewise, if all the numbers have the same frequency (
ccnt[mx] * mx
), except for one number that is alone (ccnt[1] == 1
), we can remove this single occurrence to match all the others.
We repeat these checks at each step and update the answer everytime we find a longer valid prefix. After iterating through the array, the value in ans
will be the length of the longest possible prefix satisfying the problem condition.
Solution Approach
The solution uses a couple of key data structures along with some logical checks that help execute the strategy described in the intuition effectively.
Data Structures
-
Counter
cnt
: This is a dictionary that keeps track of the occurrences of each element in the prefix of the arraynums
. Ifv
is an element innums
, thencnt[v]
will tell us how many timesv
has appeared so far. -
Counter
ccnt
: This is a dictionary that keeps track of the count of the frequencies themselves. It tells us how many numbers have a certain frequency. Iff
is a frequency, thenccnt[f]
will tell us how many numbers have appeared exactlyf
times.
Algorithm
-
Initialize the
cnt
andccnt
dictionaries (imported fromcollections
class in Python). They are both initially empty. -
Start iterating through each element
v
innums
, keeping track of the indexi
(starting from 1 instead of 0). -
At each iteration, increase the count for
v
incnt
. Ifv
has appeared before, decrease the counter for its old frequency inccnt
- since the frequency ofv
is about to increase by one. -
Update
ccnt
for the new frequency ofv
. -
Keep track of the maximum frequency seen so far in variable
mx
. This is updated to the maximum of its current value and the frequency of the current numbercnt[v]
. -
Perform the checks to see if we could make all frequencies equal by removing one element:
- Check if
mx
is 1, meaning all numbers are unique, and any prefix is valid. - Check if
ccnt[mx]
is 1 and the total count of elements with frequencymx
ormx - 1
equals the current length of the array (i
). This means we could remove the one element with frequencymx
to even out the counts. - Check if the total count of elements with frequency
mx
plus 1 equals the current length of the array and there is only one number with the frequency of 1 (ccnt[1] == 1
). We could remove the single occurrence of an element to achieve equal frequency.
- Check if
-
If any of the above conditions are true, then the current prefix (up to the index
i
) can be made to have equal frequencies by removing one element. We thus updateans
to store the maximum prefix length satisfying the condition. -
After the loop terminates,
ans
will contain the length of the longest prefix which can achieve equal frequency by removing one element, and we return this value.
Using a combination of logical checks along with efficient tracking of frequencies of the numbers and their counts using hashmaps (cnt
and ccnt
), the solution is able to identify the longest prefix satisfying the problem's conditions without having to check each possible prefix repeatedly.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take an array nums
with the values [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
and walk through the solution step by step to understand how we apply the solution approach described above.
-
We initialize our
cnt
andccnt
dictionaries empty and a variableans
for the answer. -
Start with
i = 1
, processing the first elementv = 1
.- Update
cnt[1]
from 0 to 1. Since 1 has not appeared before, there's no old frequency count to decrease inccnt
. - Update
ccnt[1]
from 0 to 1, sincecnt[1]
is now 1. - Set
mx
to 1, as it's the first and thus the highest frequency so far. - Since
mx
is 1, we updateans
to 1, which is the length of the prefix now.
- Update
-
Moving to
i = 2
with the elementv = 2
.cnt[2]
gets updated from 0 to 1.ccnt[1]
gets updated to 2 now, as there are two numbers with a frequency of 1.mx
is still 1, and thus the prefix of length 2 also satisfies the condition, soans
is updated to 2.
-
Continue with
i = 3
with the elementv = 2
.cnt[2]
increases from 1 to 2.- Decrease
ccnt[1]
from 2 to 1 since the frequency of 2 has changed. - Update
ccnt[2]
from 0 to 1. mx
updates to 2.- Now,
ccnt[mx] * mx
+ccnt[1]
is 3, which matches the length of the prefix, soans
is updated to 3.
In the interest of brevity, let’s jump to i = 10
with the element v = 4
.
-
We should have
cnt
showing{1: 1, 2: 2, 3: 3, 4: 4}
, andccnt
showing{1: 1, 2: 1, 3: 1, 4: 1}
. -
The
mx
now is 4 after processing all elements up to index 10.- Check if
mx
is 1 (false in this case). - Check if
ccnt[mx]
is 1 and the total count of elements with frequencymx
ormx - 1
equals the current index (10). This is false becauseccnt[4]
is 1, butccnt[3] * 3 + ccnt[4] * 4
is 9, not 10. - Check if
ccnt[mx] * mx + ccnt[1]
equals the current index (10) andccnt[1]
is 1. This is false becauseccnt[4] * 4 + ccnt[1]
is 17, not 10.
- Check if
-
Since no condition is met, we do not update
ans
.
After processing all elements, ans
remains 3, which is the length of the longest prefix where one can remove exactly one element to make the frequency of the remaining elements the same. Therefore, the answer for our example array [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
is 3.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def maxEqualFreq(self, nums):
5 # Counts the frequency of each number in nums
6 frequency_counter = Counter()
7 # Counts the frequency of each frequency (!) in frequency_counter
8 frequencies_count = Counter()
9 # Initialize answer and max frequency seen so far
10 answer = max_frequency = 0
11
12 # Iterate over nums, tracking the index and value with i and num respectively
13 for i, num in enumerate(nums, 1):
14 # If the current number already has a frequency, decrement its frequency count
15 if num in frequency_counter:
16 frequencies_count[frequency_counter[num]] -= 1
17
18 # Increment the frequency count of the current number and get the new count
19 frequency_counter[num] += 1
20 num_frequency = frequency_counter[num]
21
22 # Update max_frequency if necessary
23 max_frequency = max(max_frequency, num_frequency)
24
25 # Increment the count of this new frequency
26 frequencies_count[num_frequency] += 1
27
28 # Check if a single frequency dominates (all numbers have the same frequency)
29 if max_frequency == 1:
30 answer = i
31 # Check if, by removing one instance of the max frequency, all other numbers have the same frequency
32 elif frequencies_count[max_frequency] * max_frequency + frequencies_count[max_frequency - 1] * (max_frequency - 1) == i and frequencies_count[max_frequency] == 1:
33 answer = i
34 # Check if we can remove one number to satisfy the condition (all frequencies are the same except one)
35 elif frequencies_count[max_frequency] * max_frequency + 1 == i and frequencies_count[1] == 1:
36 answer = i
37
38 return answer
39
1class Solution {
2 // Initialize count arrays with enough space
3 private static int[] frequencyCounter = new int[100010];
4 private static int[] countOfFrequencyCounter = new int[100010];
5
6 public int maxEqualFreq(int[] nums) {
7 // Reset frequencies for each test case
8 Arrays.fill(frequencyCounter, 0);
9 Arrays.fill(countOfFrequencyCounter, 0);
10
11 int longestPrefixLength = 0; // Stores the answer
12 int maxFrequency = 0; // Maximum frequency of any element
13
14 // Iterate through the array elements
15 for (int i = 1; i <= nums.length; ++i) {
16 int value = nums[i - 1];
17
18 // Decrement the count of the current frequency for the value
19 if (frequencyCounter[value] > 0) {
20 --countOfFrequencyCounter[frequencyCounter[value]];
21 }
22 // Increment the frequency for the value and update the count of that frequency
23 ++frequencyCounter[value];
24 maxFrequency = Math.max(maxFrequency, frequencyCounter[value]);
25 ++countOfFrequencyCounter[frequencyCounter[value]];
26
27 // Check the conditions that need to be satisfied to consider the prefix
28
29 // All elements have frequency one, can remove any one element
30 if (maxFrequency == 1) {
31 longestPrefixLength = i;
32 }
33 // Remove one instance of the element with maximum frequency
34 else if (countOfFrequencyCounter[maxFrequency] * maxFrequency +
35 countOfFrequencyCounter[maxFrequency - 1] * (maxFrequency - 1) == i &&
36 countOfFrequencyCounter[maxFrequency] == 1) {
37 longestPrefixLength = i;
38 }
39 // Only one element that can be removed to equalize the frequency
40 else if (countOfFrequencyCounter[maxFrequency] * maxFrequency + 1 == i &&
41 countOfFrequencyCounter[1] == 1) {
42 longestPrefixLength = i;
43 }
44 }
45 // Return the length of the longest prefix where all elements can have the same frequency
46 return longestPrefixLength;
47 }
48}
49
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7 int maxEqualFreq(vector<int>& nums) {
8 unordered_map<int, int> frequencyMap; // Map to store the frequency of each number
9 unordered_map<int, int> freqCountMap; // Map to store the count of particular frequencies
10 int result = 0; // Variable to store the maximum length of subarray
11 int maxFreq = 0; // Variable to keep track of the maximum frequency
12
13 // Iterate through the array
14 for (int i = 1; i <= nums.size(); ++i) {
15 int value = nums[i - 1]; // Value of the current element
16
17 // Decrease the count of the old frequency in the freqCountMap
18 if (frequencyMap[value]) {
19 --freqCountMap[frequencyMap[value]];
20 }
21
22 // Increase the frequency of the current element
23 ++frequencyMap[value];
24 // Update the maxFreq if necessary
25 maxFreq = max(maxFreq, frequencyMap[value]);
26 // Increase the count of the new frequency in the freqCountMap
27 ++freqCountMap[frequencyMap[value]];
28
29 // Check if all numbers have the same frequency
30 if (maxFreq == 1) {
31 result = i;
32 }
33 // Check if we can delete one element to make all frequencies equal
34 else if (freqCountMap[maxFreq] * maxFreq + freqCountMap[maxFreq - 1] * (maxFreq - 1) == i && freqCountMap[maxFreq] == 1) {
35 result = i;
36 }
37 // Check if we have one number of max frequency and all others are 1
38 else if (freqCountMap[maxFreq] * maxFreq + 1 == i && freqCountMap[1] == 1) {
39 result = i;
40 }
41 }
42
43 return result; // Return the length of longest subarray with max equal frequency
44 }
45};
46
1function maxEqualFreq(nums: number[]): number {
2 const length = nums.length;
3 const frequencyMap = new Map<number, number>();
4
5 // Fill the frequency map with the occurrences of each number in nums array
6 for (const num of nums) {
7 frequencyMap.set(num, (frequencyMap.get(num) ?? 0) + 1);
8 }
9
10 // Iterate backward to find the longest prefix of nums with all numbers having same frequency
11 for (let index = length - 1; index > 0; index--) {
12 for (const key of frequencyMap.keys()) {
13 // Decrease the frequency of current key to check for equal frequency
14 frequencyMap.set(key, frequencyMap.get(key)! - 1);
15
16 let frequency = 0; // Store the frequency of the first non-zero occurrence.
17 // Find the first non-zero frequency to compare with others.
18 for (const value of frequencyMap.values()) {
19 if (value !== 0) {
20 frequency = value;
21 break;
22 }
23 }
24
25 let isValid = true; // Flag to check validity of equal frequency
26 let sum = 1; // Start with 1 to consider the decreased frequency
27
28 // Check if all non-zero frequencies are the same as the first non-zero frequency
29 for (const value of frequencyMap.values()) {
30 if (value !== 0 && value !== frequency) {
31 isValid = false;
32 break;
33 }
34 sum += value;
35 }
36
37 // If all nonzero frequencies are equal, return the sum as the max length
38 if (isValid) {
39 return sum;
40 }
41
42 // Restore the decreased frequency before moving to the next key
43 frequencyMap.set(key, frequencyMap.get(key)! + 1);
44 }
45
46 // After checking all keys, decrease the frequency of the number at current index
47 frequencyMap.set(nums[index], frequencyMap.get(nums[index])! - 1);
48 }
49
50 // If no solution found, return 1 (single number's frequency is always equal)
51 return 1;
52}
53
Time and Space Complexity
Time Complexity
The time complexity of the provided code is O(N)
where N
is the length of the nums
list. This is because the code iterates through each element of the nums
list exactly once, performing a constant amount of work for each element concerning updating the cnt
and ccnt
Counters, and computing the maximum frequency mx
. Every operation inside the loop—such as checking if v
is in cnt
, updating counters, and the conditional checks—is done in constant time, assuming that the counter operations are O(1) on average due to the hashing mechanism used.
Space Complexity
The space complexity of the provided code is O(N)
as well. The cnt
and ccnt
Counters will each store elements proportional to the number of distinct elements in nums
. In the worst case, if all elements of nums
are unique, the space taken by these counters will be linear in terms of the size of the input. Additionally, nums
, ans
, mx
, and other variables use a constant amount of extra space, but this does not change the overall space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time