Unique Number of Occurrences
Decide whether each value in an array occurs a different number of times by counting the values, then checking the counts for a repeat.
Problem Understanding
Unique Number of Occurrences (LeetCode 1207): given an array of integers arr, return true if the number of occurrences of each value is unique, that is, no two distinct values occur the same number of times. Otherwise return false.
Examples: [1, 2, 2, 1, 1, 3] → true (1 occurs 3 times, 2 twice, 3 once); [1, 2] → false (both occur once).
The Intuition: Count, Then Count the Counts
Two hash structures, one after the other.
- Count the values. A hash map from value to count, the tally from Valid Anagram.
- Look for a repeated count. Walk the counts with a set of the ones seen, the duplicate check from Contains Duplicate.
The first repeat answers false; if none turns up, the counts were all different.
Interactive Walkthrough
COUNT, THEN COUNT THE COUNTS
COUNT: +1
arr
i
0
1
2
3
4
5
counts (value:count)
counts seen
Distinct values
1
Counts seen
0
Answer
:
arr[0] = 1: count it, now 1
Next
arr[1] = 2: count it, now 1
arr
First every value is counted into a value:count tile, then each count is checked against the counts already seen. A clash turns red. Try Example 2, where 1 and 2 both occur once.
Dry Run Table
Input: arr = [1, 2, 2, 1, 1, 3]. Counts: {1: 3, 2: 2, 3: 1}.
| Value | Count | Count already seen? | Seen afterwards |
|---|---|---|---|
| 1 | 3 | no | {3} |
| 2 | 2 | no | {3, 2} |
| 3 | 1 | no | {3, 2, 1} |
No count repeated. Answer: true.
The Solution Template
A counting map, then a set of counts with an early return on the first repeat. The C version uses arrays, since values lie in -1000..1000 and no count exceeds 1000.
Unique Number of Occurrences Code
1var uniqueOccurrences = function(arr) {2 const counts = new Map();3 for (const x of arr) counts.set(x, (counts.get(x) ?? 0) + 1);4 const seen = new Set();5 for (const count of counts.values()) {6 if (seen.has(count)) {7 return false;8 }9 seen.add(count);10 }11 return true;12};
Edge Cases & Common Mistakes
- One distinct value: a single count cannot repeat, so the answer is true.
- Checking the values instead of the counts: the values are distinct by definition; it is the counts that must be unique.
- Negative values: fine as hash keys; an array-based count needs an offset, as in the C version.
- Sorting the counts: works, but costs O(k log k) where a set is O(k).
Summary
Count each value, then walk the counts with a set and return false on the first count already seen. O(n) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet