1207. Unique Number of Occurrences Easy

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

Approach

Input: An integer array arr

Output: Check if the number of occurrences of each value is unique

This is a Hash Table problem.

We can iterate through the array and store the frequency of each number using a hash table.

Then, extract all the values (frequencies) from the hash table into an array. Finally, use a Set to remove duplicates and check if the length of the new Set is equal to the length of the frequencies array. If they match, it means all occurrences are unique.

Implementation

python

class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        # Use Counter to count the occurrences of each element
        count = Counter(arr)
        
        # Create a set to store all occurrences
        occurrences = set()
        
        # Iterate through the occurrence count of each element in Counter
        for freq in count.values():
            # If the occurrence count already exists in the set, there's a duplicate frequency, return False
            if freq in occurrences:
                return False
            # Otherwise, add the count to the set
            occurrences.add(freq)
        
        # If all occurrence counts are unique, return True
        return True

javascript

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var uniqueOccurrences = function(arr) {
    // Use an object to store the number of times each number appears
    const map = {};

    // Iterate over the array and count frequencies
    for (let num of arr) {
        // If num has appeared already, increment by 1; otherwise initialize to 1
        map[num] = (map[num] || 0) + 1;
    }

    // Extract all occurrence counts into an array
    const values = Object.values(map);

    // Use a Set to remove duplicates, and compare lengths before and after deduping
    // If they are equal, it means all frequency counts are distinct
    // If they are not equal, it means there are duplicate frequency counts
    return [...new Set(values)].length === values.length;
};

Complexity Analysis

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

Links

1207. Unique Number of Occurrences (English)1207. 独一无二的出现次数 (Chinese)