Unique Number of Occurrences

Check whether every value's occurrence count in the array is itself unique.

Easy
Time O(N) Space O(N)
LeetCode
2 min read
hash-map hash-set counting

Problem#

Given an array arr, return true iff the number of occurrences of every value is unique — no two values appear the same number of times.

Examples#

  • [1,2,2,1,1,3]true (counts 3,2,1).
  • [1,2]false (both appear once).

Constraints#

  • 1 <= arr.length <= 1000, -1000 <= arr[i] <= 1000.

Hints#

Hint
Count, then put the counts in a set and compare sizes.

Approach#

Count occurrences with a map. Push every count into a set. The original array has unique counts iff set.size() == map.size().

Solution#

Unique Number of Occurrences
class Solution {
public:
bool uniqueOccurrences(vector<int>& arr) {
unordered_map<int,int> cnt;
for (int v : arr) ++cnt[v];
unordered_set<int> seen;
for (auto& [_, c] : cnt) {
if (!seen.insert(c).second) return false;
}
return true;
}
};

Editorial#

Two passes: one to count, one to check uniqueness. unordered_set::insert returns false when an element is already present, giving a single-line uniqueness check.

Complexity#

  • Time: O(N).
  • Space: O(N).

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.