Unique Number of Occurrences

Problem Statement

In this task, you are provided with an array of integers named arr. The objective is to determine if the number of occurrences of each value within the array is unique. Specifically, you need to return true if no two different values in the array have the same frequency. Conversely, if there is at least one frequency that is shared between two or more values, you should return false. This problem challenges the understanding of hash maps and frequency counting in arrays.

Examples

Example 1

Input:

arr = [1,2,2,1,1,3]

Output:

true

Explanation:

 The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

Example 2

Input:

arr = [1,2]

Output:

false

Example 3

Input:

arr = [-3,0,1,-3,1,1,1,-3,10,0]

Output:

true

Constraints

• 1 <= arr.length <= 1000
• -1000 <= arr[i] <= 1000

Approach and Intuition

To solve the problem, we can follow these steps:

1. Initialize a dictionary (or hash map) to count the frequency of each number in the array.
2. Traverse the array, and for each element, increase its count in the dictionary.
3. After counting the frequencies of all the numbers, we need to check if the frequencies are unique. To do this, transition the values (which represent the frequencies) from the dictionary to a set. The property of a set is that it only contains unique items.
4. If the size of the set (of frequencies) is the same as the number of unique elements in the dictionary, then no two numbers have the same frequency. In this case, return true.
5. If the size of the set is less than the number of unique elements in the dictionary, then at least two numbers have the same frequency. Hence, return false.

Given the constraints of the problem where the maximum possible length of the array is 1000, and element values ranging from -1000 to 1000, this approach is efficient. The primary computational operations involve traversing the array and dictionary operations (both insertion and lookup), which are generally efficient. The steps capitalize on simple data structures like dictionaries and sets to ensure a solution that is easy to understand and implement.

Solutions

class Solution {
public:
    bool distinctOccurrences(vector<int>& elements) {
        unordered_map<int, int> occurrenceMap;
        for (int element : elements) {
            occurrenceMap[element]++;
        }
            
        unordered_set<int> countsSet;
        for (auto count : occurrenceMap) {
            countsSet.insert(count.second);
        }
            
        return countsSet.size() == occurrenceMap.size();
    }
};

class Solution {
    public boolean checkUniqueOccurrences(int[] elements) {
        // Collect element frequencies in hashmap
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int element : elements) {
            frequencyMap.put(element, frequencyMap.getOrDefault(element, 0) + 1);
        }
            
        // Collect unique frequencies using hashset
        Set<Integer> uniqueFrequencies = new HashSet<>(frequencyMap.values());
            
        // Check if the unique frequencies count matches the original frequency map's size
        return frequencyMap.size() == uniqueFrequencies.size();
    }
}