Watch 10 video solutions for Unique Number of Occurrences, a easy level problem involving Array, Hash Table. This walkthrough by Nick White has 21,022 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |