1224. Maximum Equal Frequency

HardArrayHash Table
Leetcode Link

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:

  1. The frequency of each number in the prefix (cnt).
  2. 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:

  1. If the maximum frequency (mx) is 1, which means all elements are unique, any prefix is valid by removing any one of them.
  2. 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.
  3. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

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

  1. Counter cnt: This is a dictionary that keeps track of the occurrences of each element in the prefix of the array nums. If v is an element in nums, then cnt[v] will tell us how many times v has appeared so far.

  2. 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. If f is a frequency, then ccnt[f] will tell us how many numbers have appeared exactly f times.

Algorithm

  • Initialize the cnt and ccnt dictionaries (imported from collections class in Python). They are both initially empty.

  • Start iterating through each element v in nums, keeping track of the index i (starting from 1 instead of 0).

  • At each iteration, increase the count for v in cnt. If v has appeared before, decrease the counter for its old frequency in ccnt - since the frequency of v is about to increase by one.

  • Update ccnt for the new frequency of v.

  • 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 number cnt[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 frequency mx or mx - 1 equals the current length of the array (i). This means we could remove the one element with frequency mx 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.

  • 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 update ans 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Example 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 and ccnt dictionaries empty and a variable ans for the answer.

  • Start with i = 1, processing the first element v = 1.

    • Update cnt[1] from 0 to 1. Since 1 has not appeared before, there's no old frequency count to decrease in ccnt.
    • Update ccnt[1] from 0 to 1, since cnt[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 update ans to 1, which is the length of the prefix now.

  • Moving to i = 2 with the element v = 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, so ans is updated to 2.

  • Continue with i = 3 with the element v = 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, so ans 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}, and ccnt 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 frequency mx or mx - 1 equals the current index (10). This is false because ccnt[4] is 1, but ccnt[3] * 3 + ccnt[4] * 4 is 9, not 10.
    • Check if ccnt[mx] * mx + ccnt[1] equals the current index (10) and ccnt[1] is 1. This is false because ccnt[4] * 4 + ccnt[1] is 17, not 10.

  • 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
Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫