Unique Occurrences Algorithms for Numbers

Given a list of integers nums, return whether the number of occurrences of every value in the array is unique.

Note: Numbers can be negative.
Constraint
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [5, 3, 1, 8, 3, 1, 1, 8, 8, 8]
Output
True
Explanation
There’s 1 occurrence of 5, 2 occurrences of 3, 3 occurrences of 1, and 4 occurrences of 8. All number of occurrences are unique.

Example 2
Input
nums = [-3, -1, -1, -1, -2, -2]
Output
True
Explanation
There’s 1 occurrence of -3, 2 occurrences of -2, and 3 occurrences of -1. All number of occurrences are unique.

Example 3
Input
nums = [3, 1, 1, 2, 2, 2, 3]
Output
False
Explanation
There are 2 occurrences of 1, and 2 occurrences of 3. So the number of occurrences here is not unique.

Checking Unique Number Occurences using Hash Table/Set in C++

We can use a hash table to store the numbers and their frequencies. Then we can use another hash table (hash set e.g. unordered_set in C++) to check if we have duplicate frequencies.

1
2
3
4
5
6
7
8
9
10
11
12

bool uniqueOccurences(vector<int>& nums) {
    unordered_map<int, int> data;
    for (const auto &n: nums) {
        data[n] ++;
    }
    unordered_set<int> data2;
    for (auto &[a, b]: data) {
        if (data2.count(b)) return false;
        data2.insert(b);
    }
    return true;
}

bool uniqueOccurences(vector<int>& nums) {
    unordered_map<int, int> data;
    for (const auto &n: nums) {
        data[n] ++;
    }
    unordered_set<int> data2;
    for (auto &[a, b]: data) {
        if (data2.count(b)) return false;
        data2.insert(b);
    }
    return true;
}

The time complexity is O(N) and the space complexity is O(N). We can actually check the size of the set and the map to see if they are equal:

1
2
3
4
5
6
7
8
9
10
11

bool uniqueOccurences(vector<int>& nums) {
    unordered_map<int, int> data;
    for (const auto &n: nums) {
        data[n] ++;
    }
    unordered_set<int> data2;
    for (auto &[a, b]: data) {
        data2.insert(b);
    }
    return data2.size() == data.size();
}

bool uniqueOccurences(vector<int>& nums) {
    unordered_map<int, int> data;
    for (const auto &n: nums) {
        data[n] ++;
    }
    unordered_set<int> data2;
    for (auto &[a, b]: data) {
        data2.insert(b);
    }
    return data2.size() == data.size();
}

Python Oneliner to Check Unique Occurences

Let’s use Counter object in Python to automatically constructure the hash table with key value pairs where key is the numbers, and the value is the corresponding frequencies.

Then, we can compare the size of the hash table (number of the unique numbers) and the size of the set built from the values i.e. frequencies.

1
2
3
4

class Solution:
    def solve(self, nums):
        data = Counter(nums)
        return len(data) == len(set(data.values()))

class Solution:
    def solve(self, nums):
        data = Counter(nums)
        return len(data) == len(set(data.values()))

–EOF (The Ultimate Computing & Technology Blog) —