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] <= 1000Problem Overview: You receive an integer array and need to verify whether the frequency of every value is unique. If two different numbers appear the same number of times, the result is false. Otherwise, return true.
Approach 1: Hash Map and Set (O(n) time, O(n) space)
The direct solution uses a frequency counter. Iterate through the array and store counts in a hash map where the key is the number and the value is its occurrence count. After building the map, iterate over the frequency values and insert them into a set. A set automatically removes duplicates, so if any frequency repeats, the set size will be smaller than the number of unique elements.
This works because hash lookups and insertions run in constant average time. The key insight is separating the problem into two steps: counting occurrences and verifying uniqueness of those counts. The array is scanned once to build frequencies and once more to validate uniqueness, giving O(n) time complexity and O(n) space for the hash structures. This method is commonly implemented with a hash table from the Hash Table family while iterating over the Array.
Approach 2: Sorting and Comparison (O(n log n) time, O(n) space)
Another option avoids a set by sorting the frequency values. First compute counts using a hash map. Extract the frequencies into a list and sort them. After sorting, duplicate frequencies become adjacent, so a single linear scan can detect whether two consecutive counts are equal.
The main cost comes from sorting the frequency list, which takes O(k log k) where k is the number of distinct elements. In the worst case k = n, giving O(n log n) time complexity. Space usage remains O(n) due to the frequency map and the list used for sorting. This approach is sometimes preferred when you already rely on sorting for additional processing or want a simple comparison-based check.
Recommended for interviews: The hash map + set approach is the expected solution. It demonstrates correct use of frequency counting and constant-time membership checks. Interviewers often accept the sorting method, but the linear-time hash solution shows stronger understanding of hash-based data structures and optimal complexity.
In this approach, we will first traverse the array to count the occurrences of each element using a hash map. Then, we will use a set to check if these occurrences are unique. If the size of the set matches the size of the occurrence counts, it implies all occurrences are unique.
In the C implementation, we use an array count to store the frequency of each element adjusted by 1000 to handle negative indices. The hash array is used to ensure all frequencies are unique.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), since we're using fixed-size arrays.
This alternative approach starts by counting occurrences just like the first one. After that, it stores these counts in a list, sorts the list, and then checks for any consecutive equal elements, which would indicate duplicate occurrences.
In the C implementation using sorting, we use qsort to sort the frequency array and then check if any consecutive elements are equal.
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(1), since we work within fixed-sized arrays.
We use a hash table cnt to count the frequency of each number in the array arr, and then use another hash table vis to count the types of frequencies. Finally, we check whether the sizes of cnt and vis are equal.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array arr.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Hash Map and Set | Time Complexity: O(n), where n is the length of the array. |
| Sorting and Comparison | Time Complexity: O(n log n), due to sorting. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map and Set | O(n) | O(n) | General case. Fastest solution using frequency counting and set uniqueness check. |
| Sorting and Comparison | O(n log n) | O(n) | Useful when frequency values are already being sorted or when avoiding a set. |
LeetCode 1207. Unique Number of Occurrences (Algorithm Explained) • Nick White • 21,022 views views
Watch 9 more video solutions →Practice Unique Number of Occurrences with our built-in code editor and test cases.
Practice on FleetCode