1207. Unique Number of Occurrences
Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.
Example 1:
Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.
Example 2:
Input: arr = [1,2]
Output: false
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
From: LeetCode
Link: 1207. Unique Number of Occurrences
Solution:
Ideas：
We can use a hash table (or an array, considering the constraints) to count occurrences. Then, we use another hash table to check for the uniqueness of these counts.
- occurrences is an array indexed from -1000 to 1000 (shifted by 1000 to accommodate negative numbers), used to count the occurrences of each integer in arr.
- seen is a boolean array used to track if a specific occurrence count has been seen before.
- We first iterate through the arr to count the occurrences of each number.
- Then, we iterate through the occurrences array to check if any count has been seen before. If a count is repeated, we return false. If we finish the loop without finding any duplicate counts, we return true.
Code:
bool uniqueOccurrences(int* arr, int arrSize) {
int occurrences[2001] = {
0}; // Array to count occurrences, offset by 1000 for negative numbers
bool seen[1001] = {
false}; // Array to track if an occurrence count has been seen
// Count occurrences of each number
for (int i = 0; i < arrSize; i++) {
occurrences[arr[i] + 1000]++;
}
// Check for unique occurrences
for (int i = 0; i < 2001; i++) {
if (occurrences[i] > 0) {
if (seen[occurrences[i]]) {
// If we have already seen this count, it's not unique
return false;
}
seen[occurrences[i]] = true;
}
}
return true;
}
