Wednesday, April 17, 2024 9:32 EDT

Leetcode 1207. Unique Number of Occurrences (Easy)

Approach
A map makes the most sense here. Keeping track of how many occurrences of each item in the array is easy with a map. Unordered maps are more efficient and we don't care about order in this instance. After I loop the input vector and count the occurrences, I create a set of items. Inherently, sets do not allow duplicate values so if we can't insert the value (second/number of occurrences) from the map, we can assume a duplicate value was found and return false. Otherwise, return true.

Complexity
Time Complexity: O(n log n)
Space Complexity: O(n)

Code

class Solution {
public:

    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map<int, int> occ;
        for(int num : arr){
            occ[num]++;
        }

        set<int> seen;

        for(auto& keyValue : occ){
            if(!seen.insert(keyValue.second).second) {
                return false;
            }
        }
        return true;
    }
};