1207. Unique Number of Occurrences

[songyy5517]

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

Intuition This problem can be broken down into two subtasks. First, we need to calculate the ocurrences of each element in the array. Then we have to determine whether there exist same ocurrences. For the first task, we can use hashmap to record the occurences of each element when looping though the array. For the second task, considering the non-repetitive property of Set, we can use a hashset to store all the occurence values. If the size of hashset is the same as the size of hashmap, then the occurences of each value is unique, return true; vice versa.

[songyy5517]

Approach: HashMap & HashSet

1. Exception handling;
2. Define hashmap;
3. Iterate over the array and calculate the occurences of each element using hashmap;
4. Generate a hashset through the value set of the hashmap;
5. If the size of the hashset is equal to the size of the hashmap, return true; vice versa.

Complexity Analysis

• Time complexity: $O(N)$ , calculating the occurence of each element takes involves the travarsal of the array, which takses $O(N)$ time;
• Space complexity: $O(N)$ , addtionally define $O(N)$ - sized hashmap & hashset.

[songyy5517]

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        // Intuition: HashMap & HashSet.
        // 1. Exception handling
        if (arr == null || arr.length == 0)
            return false;

        // 2. Define HashMap
        HashMap<Integer, Integer> hm = new HashMap();

        // 3. Calculate the ocurrences
        for (int i : arr)
            hm.put(i, hm.getOrDefault(i, 0) + 1);

        return hm.size() == new HashSet(hm.values()).size();
    }
}

[songyy5517]

2024/5/16

• Use getOrDefualt to update the hashmap;
• Hashset can be generated directly via hm.values()