Unique Number of Occurrences — Problem & Solution
Unique Number of Occurrences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Unique Number of Occurrences is an easy coding problem on arrays and hash table, asked in Amazon and TCS interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table
- Asked at: Amazon, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of integers arr, return true if the number of occurrences of each value is unique — no two distinct values occur the same number of times.
Example 1
Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: 1 occurs three times, 2 twice and 3 once — all different.
Example 2
Input: arr = [1,2]
Output: false
Explanation: Both values occur once.
Example 3
Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true
Constraints
1 <= arr.length <= 1000-1000 <= arr[i] <= 1000
Hints for Unique Number of Occurrences
Hint 1
Two passes: count the values, then check the counts for duplicates.
Hint 2
A set of the counts is the cleanest way to test uniqueness.
Hint 3
Return
falsethe moment a count repeats.
How to solve Unique Number of Occurrences
Build the frequency map, then treat its values as the thing to deduplicate. If inserting a count into a set ever collides, two values share a frequency.
Approach
- Count occurrences of every distinct value.
- Walk the counts, inserting each into a set.
- Return
falseon the first collision,trueotherwise.
Why it works
Uniqueness of the multiset of counts is exactly the property asked for, and a set answers it in one linear pass.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Comparing the count map's size with the array length answers a different question.
- Sorting the counts and checking neighbours also works — just remember to sort the values, not the keys.
Reference solution
Python
from typing import List
def uniqueOccurrences(arr: List[int]) -> bool:
count = {}
for x in arr:
count[x] = count.get(x, 0) + 1
counts = list(count.values())
return len(counts) == len(set(counts))Java
public static boolean uniqueOccurrences(int[] arr) {
HashMap<Integer, Integer> count = new HashMap<>();
for (int x : arr) count.put(x, count.getOrDefault(x, 0) + 1);
HashSet<Integer> seen = new HashSet<>();
for (int c : count.values()) {
if (!seen.add(c)) return false;
}
return true;
}C++
bool uniqueOccurrences(vector<int>& arr) {
unordered_map<int, int> count;
for (int x : arr) count[x]++;
unordered_set<int> seen;
for (auto& e : count) {
if (seen.count(e.second)) return false;
seen.insert(e.second);
}
return true;
}JavaScript
var uniqueOccurrences = function(arr) {
const count = {};
for (let i = 0; i < arr.length; i++) {
const k = String(arr[i]);
count[k] = (count[k] || 0) + 1;
}
const seen = {};
const keys = Object.keys(count);
for (let i = 0; i < keys.length; i++) {
const c = String(count[keys[i]]);
if (seen[c] === true) return false;
seen[c] = true;
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets