Unique Number of Occurrences
Check whether every value's occurrence count in the array is itself unique.
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#
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; }};func uniqueOccurrences(arr []int) bool { cnt := map[int]int{} for _, v := range arr { cnt[v]++ } seen := map[int]bool{} for _, c := range cnt { if seen[c] { return false } seen[c] = true } return true}from collections import Counterfrom typing import List
class Solution: def uniqueOccurrences(self, arr: List[int]) -> bool: counts = Counter(arr).values() return len(set(counts)) == len(counts)function uniqueOccurrences(arr) { const cnt = new Map(); for (const v of arr) cnt.set(v, (cnt.get(v) ?? 0) + 1); const seen = new Set(); for (const c of cnt.values()) { if (seen.has(c)) return false; seen.add(c); } return true;}class Solution { public boolean uniqueOccurrences(int[] arr) { Map<Integer, Integer> cnt = new HashMap<>(); for (int v : arr) cnt.merge(v, 1, Integer::sum); Set<Integer> seen = new HashSet<>(); for (int c : cnt.values()) { if (!seen.add(c)) return false; } return true; }}function uniqueOccurrences(arr: number[]): boolean { const cnt = new Map<number, number>(); for (const v of arr) cnt.set(v, (cnt.get(v) ?? 0) + 1); const seen = new Set<number>(); for (const c of cnt.values()) { if (seen.has(c)) return false; seen.add(c); } 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#
Related#