Unique Number of Occurrences
Unique Number of Occurrences: return true if the number of occurrences of every value in the array is unique — that is, no two distinct values appear the same number of times.
- 1 <= arr.length <= 1000
- -1000 <= arr[i] <= 1000
Intuition
Unique number of occurrences checks whether every value in an array occurs a different number of times. Two values may not share an occurrence count. The problem is two counting steps stacked, which is what makes it a useful exercise: - Count how many times each value appears, then check whether those counts are themselves all distinct. The first step is an ordinary frequency map. The second is a duplicate check on the map's values rather than its keys — which is the part that reads oddly at first, since the counts become the data. The cleanest test compares sizes. Put the counts into a set: if the set is smaller than the number of distinct values, two values shared a count and the answer is false. Equal sizes mean every count was unique. That comparison avoids any explicit loop over pairs, and it is a general technique — comparing a collection's size against its set's size is the standard idiom for detecting duplicates. An alternative inserts each count into a set one at a time and returns false the moment an insertion finds the value already present. Equivalent, with an early exit. The array can contain negative values, so a fixed-size array indexed by value is unsafe unless offset. A hash map avoids the issue entirely. Sorting the counts and scanning for adjacent equals also works at O(n log n), but the set approach is linear and simpler. Two passes give O(n) time and O(n) space for the map and set.
Two-stage counting — count the items, then count the counts — appears whenever a question is about the distribution rather than the data. The len(x) == len(set(x)) idiom is the reusable uniqueness test, and it also settles Contains Duplicate and Determine if Two Strings Are Close.
Approach
Before reading on: after you have the occurrence count of each value, what exactly are you comparing — the values, or the counts? Then find a one-line way to test that a collection has no repeats. Aim for O(n).
Count value frequencies
Build a map from each value to how many times it appears. This is the ordinary first half of the problem.
Treat the counts as data
The duplicate check runs on the map's values, not its keys. The occurrence counts themselves become the collection being examined.
Compare sizes
Put the counts into a set. A smaller set means two values shared a count, so the answer is false; equal sizes mean all counts were distinct.
Recognise the idiom
Comparing a collection's size against its set's size is the standard way to detect duplicates without an explicit pairwise loop.
Use a map, not an array
The array can contain negative values, so indexing a fixed array by value is unsafe without an offset. A hash map sidesteps this.
Cost of the approach
Two linear passes give O(n) time and O(n) space for the frequency map and the set of counts.
Solution & live demo
Common pitfalls
Testing uniqueness of the values instead of the counts
return len(arr) == len(set(arr))
return len(frequencies) == len(set(frequencies))
That checks whether the elements are distinct, which is a different problem entirely. [1,2,2,1,1,3] has repeated elements yet perfectly unique occurrence counts — the correct answer is true.
Comparing counts pairwise
for a in counts.values():
for b in counts.values():
...return len(frequencies) == len(set(frequencies))
Correct but O(k²), and it needs careful handling to avoid comparing an entry with itself. The set comparison expresses the same idea in one line with no index bookkeeping.
Using the set of the map instead of its values
return len(counts) == len(set(counts))
return len(frequencies) == len(set(frequencies))
Iterating a dict yields its keys, which are distinct by construction — so this always returns true. The counts live in .values().
Edge cases
Every count is 1, so three values share a frequency and the answer is false.
One count of 1, trivially unique, so true.
Both count 2 — the set shrinks from two entries to one and the answer is false.
A hash map keys on any integer, so signs are irrelevant.
A single count of 3 is unique by definition, so true.