14 Unique number of occurences

Unique Number of Occurrences - LeetCodeLeetCode

LeetCode: Unique Number of Occurrences

Question

Given an array of integers arr, return true if the number of occurrences of each value in the array is unique, or false otherwise.

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

Using map

Logic

1. Create a map and store frequencies of

2. Create a second map and store the frequency of frequencies.

3. If at any point frequency repeats then return false

4. else return true

Code

bool uniqueOccurrences(vector<int>& arr) {
    map<int, int> frequencyOfElements;

    for(int x: arr)
        frequencyOfElements[x]++;

    map<int, int> frequencyOfFrequencies;

    for(auto p: frequencyOfElements) 
        if(++frequencyOfFrequencies[p.second] > 1)
            return false;

    return true; 

}

Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$