1207. Unique Number of Occurrences

Description

The function checks if the occurrences of each element in an array are unique. Given an array of integers, it determines whether the frequency of each element appears only once across the entire array. The result is true if all frequencies are unique, otherwise, it returns false.

Intuition

The intuition behind the solution is to count the occurrences of each element and then verify if these counts are unique. If any two different elements have the same count, then the occurrences are not unique.

Approach

1. Count Occurrences: Use a map or dictionary to count how many times each element appears in the array.
2. Check Uniqueness: Store these counts in a set. Since sets do not allow duplicate values, if all counts are unique, the size of the set will match the size of the map or dictionary.
3. Return the Result: Compare the size of the set to the size of the map or dictionary. If they are equal, return true, otherwise return false.

Complexity

Time Complexity:

O(n), where n is the length of the array. We traverse the array once to count occurrences and then traverse the map or dictionary once to populate the set.

Space Complexity:

O(n), due to the space required to store the counts in a map or dictionary and the set.

Code

C++

class Solution {
public:
    bool uniqueOccurrences(vector& arr) {
        unordered_map map;
        
        for (int num : arr) {
            map[num]++;
        }
        
        unordered_set set;
        for (auto it : map) {
            set.insert(it.second);
        }
        
        return set.size() == map.size();
    }
};

Python

class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        count_map = {}
        
        for num in arr:
            if num in count_map:
                count_map[num] += 1
            else:
                count_map[num] = 1
        
        count_set = set(count_map.values())
        
        return len(count_set) == len(count_map)

Java

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        HashMap map = new HashMap<>();
        
        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        
        HashSet set = new HashSet<>(map.values());
        
        return set.size() == map.size();
    }
}

JavaScript

var uniqueOccurrences = function (arr) {

    let map = new Map();
    
    for (let num of arr) {
        if (map.has(num)) {
            map.set(num, (map.get(num) + 1));
        } else {
            map.set(num, 1);
        }
    }
    let set = new Set(map.values());
    return set.size === map.size;
};