Problem Description

You are given an array of integers arr. Your task is to determine if the frequency of each unique value in the array is distinct.

In other words, count how many times each number appears in the array. If all these occurrence counts are different from each other, return true. If any two numbers have the same occurrence count, return false.

For example:

• If the array is [1, 2, 2, 1, 1, 3], the number 1 appears 3 times, 2 appears 2 times, and 3 appears 1 time. Since the frequencies (3, 2, 1) are all different, the answer is true.
• If the array is [1, 2], both 1 and 2 appear exactly 1 time. Since two numbers have the same frequency, the answer is false.

The solution uses a hash table to count the frequency of each number in the array, then checks if all frequency values are unique by comparing the number of distinct frequencies with the total number of unique elements.

Intuition

The key insight is that we need to check if all frequency counts are unique. This is essentially a two-step process:

1. First, count how many times each number appears in the array
2. Then, check if these counts themselves are all different

Think of it this way: if we have counts like {1: 3, 2: 2, 3: 1} (meaning 1 appears 3 times, 2 appears 2 times, 3 appears 1 time), we need to verify that the values [3, 2, 1] are all distinct.

The clever part is realizing that to check if all frequencies are unique, we can use a set. Sets automatically remove duplicates, so if we put all frequency values into a set and the set has the same size as the original collection of frequencies, then all frequencies must be unique.

For example:

• If frequencies are [3, 2, 1], converting to a set gives {3, 2, 1} with size 3, same as original
• If frequencies are [2, 2, 1], converting to a set gives {2, 1} with size 2, different from original size 3

This leads to the elegant solution: len(set(cnt.values())) == len(cnt). If the number of unique frequencies equals the number of unique elements in the array, then each element has a distinct occurrence count.

Solution Approach

The solution uses a hash table approach to solve this problem efficiently.

Step 1: Count Frequencies We use Python's Counter from the collections module to create a hash table cnt that counts the frequency of each number in the array. After this step, cnt contains key-value pairs where the key is a number from the array and the value is how many times it appears.

For example, if arr = [1, 2, 2, 1, 1, 3], then cnt = {1: 3, 2: 2, 3: 1}.

Step 2: Check Uniqueness of Frequencies To verify if all frequencies are unique, we extract all the frequency values using cnt.values() and convert them to a set using set(cnt.values()). Since sets automatically eliminate duplicates, if any two elements had the same frequency, the set would be smaller than the original collection.

Step 3: Compare Sizes We compare the size of the set of frequencies with the size of the original counter:

• len(set(cnt.values())) gives us the number of unique frequencies
• len(cnt) gives us the number of distinct elements in the original array

If these two values are equal, it means each frequency value is unique, so we return true. Otherwise, we return false.

Time Complexity: O(n) where n is the length of the array, as we iterate through the array once to count frequencies.

Space Complexity: O(n) in the worst case when all elements are unique, requiring space for the hash table to store all elements and their counts.

Example Walkthrough

Let's walk through the solution with the array [1, 2, 2, 1, 1, 3].

Step 1: Count the frequency of each element

We iterate through the array and count occurrences:

• 1 appears: at indices 0, 3, 4 → 3 times
• 2 appears: at indices 1, 2 → 2 times
• 3 appears: at index 5 → 1 time

Our frequency counter becomes: {1: 3, 2: 2, 3: 1}

Step 2: Extract the frequency values

From our counter, we get the values: [3, 2, 1]

Step 3: Check if all frequencies are unique

We convert the frequency values to a set: {3, 2, 1}

• Original number of unique elements: len(cnt) = 3 (we have three distinct numbers: 1, 2, 3)
• Number of unique frequencies: len(set([3, 2, 1])) = 3 (all frequencies are different)

Step 4: Compare and return result

Since 3 == 3, all frequencies are unique, so we return true.

Counter-example: If we had [1, 2]:

• Frequency counter: {1: 1, 2: 1}
• Frequency values: [1, 1]
• Set of frequencies: {1} (duplicates removed)
• len(set([1, 1])) = 1 but len(cnt) = 2
• Since 1 ≠ 2, we return false

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

• Creating the Counter object requires iterating through all n elements in the array to count occurrences: O(n)
• cnt.values() returns a view of the values in O(1) time
• Converting values to a set requires iterating through all unique counts (at most n values): O(k) where k is the number of unique elements, and k ≤ n
• len(set(cnt.values())) and len(cnt) are both O(1) operations after the set is created
• Overall time complexity: O(n) + O(k) = O(n) since k ≤ n

Space Complexity: O(n)

• The Counter object stores at most n key-value pairs (in the worst case where all elements are unique): O(n)
• Creating a set from the values requires additional space for at most k unique occurrence counts, where k ≤ n: O(k)
• Overall space complexity: O(n) + O(k) = O(n) since k ≤ n

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Problem Requirements

The Mistake: A common misunderstanding is thinking we need to check if all elements in the array are unique, rather than checking if all frequency counts are unique. Someone might incorrectly write:

def uniqueOccurrences(self, arr: List[int]) -> bool:
    return len(set(arr)) == len(arr)  # Wrong! This checks if elements are unique

The Fix: Focus on the frequencies, not the elements themselves. The correct approach counts occurrences first, then checks if those counts are unique.

Pitfall 2: Incorrect Frequency Comparison Logic

The Mistake: Some developers might try to compare frequencies incorrectly by iterating through and checking duplicates manually, leading to inefficient or buggy code:

def uniqueOccurrences(self, arr: List[int]) -> bool:
    frequency_map = Counter(arr)
    freq_list = list(frequency_map.values())
  
    # Inefficient nested loop approach
    for i in range(len(freq_list)):
        for j in range(i + 1, len(freq_list)):
            if freq_list[i] == freq_list[j]:
                return False
    return True

The Fix: Use a set to check uniqueness in O(n) time instead of O(n²) with nested loops. The set automatically handles duplicate detection.

Pitfall 3: Not Handling Edge Cases

The Mistake: Forgetting to consider edge cases like empty arrays or single-element arrays:

def uniqueOccurrences(self, arr: List[int]) -> bool:
    if not arr:  # What should we return for empty array?
        return ???
    frequency_map = Counter(arr)
    return len(set(frequency_map.values())) == len(frequency_map)

The Fix: The given solution actually handles these cases correctly:

• Empty array: Counter([]) returns an empty Counter, and both len(set()) and len(Counter()) equal 0, returning True
• Single element: Returns True as there's only one frequency

Pitfall 4: Manual Frequency Counting Errors

The Mistake: Attempting to count frequencies manually instead of using Counter, which can lead to errors:

def uniqueOccurrences(self, arr: List[int]) -> bool:
    frequency_map = {}
    for num in arr:
        frequency_map[num] += 1  # KeyError if num not in dictionary!
    return len(set(frequency_map.values())) == len(frequency_map)

The Fix: Either use Counter which handles this automatically, or properly initialize dictionary entries:

frequency_map = {}
for num in arr:
    frequency_map[num] = frequency_map.get(num, 0) + 1