Problem
Given an integer array arr, returntrue if the number of occurrences of each value in the array is unique. Otherwise, return false.
For example, if a value occurs
2 times and another value also occurs 2 times, the occurrence counts are not unique.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
arr = [1,2,2,1,1,3]Output
trueExample 2
Input
arr = [1,2]Output
falseSolution
This solution uses a HashMap to count the frequency of each distinct value and a HashSet to track the frequencies that have already been seen.First, we store the occurrence count of every value in the
HashMap. We then iterate through the frequency values. If a frequency already exists in the HashSet, two different values have the same number of occurrences, so we return false. Otherwise, we add the frequency to the set.
class Solution {
public boolean uniqueOccurrences(int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : arr) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
Set<Integer> set = new HashSet<>();
for (int count : map.values()) {
if (!set.add(count)) {
return false;
}
}
return true;
}
}Complexity
We traverse the array once to calculate frequencies and then traverse the frequency values, so the average time complexity isO(n), where n is the length of the array.
The HashMap and HashSet store information about the distinct values and their frequencies, so the extra space complexity is
O(n).
