Solution Explanation: Unique Number of Occurrences

The problem asks to determine if the number of occurrences of each unique element in an array is also unique. This means we need to check if the frequencies of elements are distinct.

Approach:

The most efficient approach leverages hash tables (or dictionaries in Python) to count element frequencies and then check for uniqueness among those frequencies.

1. Count Occurrences: We first iterate through the input array arr and count the occurrences of each element using a hash table (e.g., Counter in Python, HashMap in Java, unordered_map in C++, Map in TypeScript). The keys of this hash table represent the unique elements in the array, and the values represent their corresponding frequencies.

2. Check for Unique Frequencies: Next, we need to verify that all these frequencies are unique. We can achieve this by:

   • Method 1 (Efficient): Create a Set (or similar data structure in the chosen language) to store the frequencies. If adding a frequency to the Set fails (because it already exists), we know the frequencies are not unique, and we can return false. If we successfully add all frequencies to the Set, it means they are unique, and we return true. This method efficiently handles the uniqueness check because Set operations have O(1) average-case time complexity.

   • Method 2 (Less Efficient): We can also create a second hash table to store the frequencies and their counts (how many times each frequency appears). After counting frequencies, we iterate through this second hash table. If any frequency has a count greater than 1, it indicates non-uniqueness, and we return false.

3. Return Result: After checking for unique frequencies, the function returns true if all frequencies are unique; otherwise, it returns false.

Time Complexity Analysis:

• The first step (counting occurrences) takes O(n) time, where n is the length of the input array, because we iterate through the array once.
• The second step (checking for unique frequencies using a Set) also takes O(m) time on average, where m is the number of unique elements in the array. In the worst case (all elements are unique), m = n. However, often m is significantly smaller than n.
• Therefore, the overall time complexity is dominated by the linear traversals, making it O(n) on average.

Space Complexity Analysis:

The space complexity is determined by the size of the hash tables used to store the counts. In the worst case (all elements are unique), the space complexity will be O(n).

Code Examples:

The provided code examples in Python, Java, C++, Go, and TypeScript demonstrate the efficient approach (Method 1) using sets to check for unique frequencies. They all follow the same algorithmic steps outlined above.

Example (Python):

from collections import Counter
 
class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        cnt = Counter(arr)  # Count occurrences
        return len(set(cnt.values())) == len(cnt)  # Check if frequencies are unique using a set
 

This Python code uses the Counter object for efficient counting and then directly checks if the number of unique frequency values (obtained using set) matches the number of unique elements. This compactly implements the solution. The other language examples follow similar logic adapted to their respective syntax and data structures.