In this approach, we will first traverse the array to count the occurrences of each element using a hash map. Then, we will use a set to check if these occurrences are unique. If the size of the set matches the size of the occurrence counts, it implies all occurrences are unique.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), since we're using fixed-size arrays.
1#include <stdio.h>
2#include <stdbool.h>
3#include <stdlib.h>
4
5bool uniqueOccurrences(int* arr, int arrSize) {
6 int count[2001] = {0};
7 int hash[1001] = {0};
8
9 for(int i = 0; i < arrSize; i++) {
10 count[arr[i] + 1000]++;
11 }
12
13 for(int i = 0; i < 2001; i++) {
14 if(count[i] > 0) {
15 if(hash[count[i]])
16 return false;
17 hash[count[i]] = 1;
18 }
19 }
20
21 return true;
22}
23
24int main() {
25 int arr[] = {1, 2, 2, 1, 1, 3};
26 int arrSize = sizeof(arr) / sizeof(arr[0]);
27 printf("%s\n", uniqueOccurrences(arr, arrSize) ? "true" : "false");
28 return 0;
29}In the C implementation, we use an array count to store the frequency of each element adjusted by 1000 to handle negative indices. The hash array is used to ensure all frequencies are unique.
This alternative approach starts by counting occurrences just like the first one. After that, it stores these counts in a list, sorts the list, and then checks for any consecutive equal elements, which would indicate duplicate occurrences.
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(1), since we work within fixed-sized arrays.
1#include <stdio.h>
2#include <stdbool.h>
3#include <stdlib.h>
4
5int cmpfunc (const void * a, const void * b) {
6 return (*(int*)a - *(int*)b);
7}
8
9bool uniqueOccurrences(int* arr, int arrSize) {
10 int count[2001] = {0};
11 int occ[1001] = {0};
12 int idx = 0;
13
14 for(int i = 0; i < arrSize; i++) {
15 count[arr[i] + 1000]++;
16 }
17
18 for(int i = 0; i < 2001; i++) {
19 if(count[i] > 0) {
20 occ[idx++] = count[i];
21 }
22 }
23
24 qsort(occ, idx, sizeof(int), cmpfunc);
25
26 for(int i = 1; i < idx; i++) {
27 if(occ[i] == occ[i - 1])
28 return false;
29 }
30
31 return true;
32}
33
34int main() {
35 int arr[] = {1, 2, 2, 1, 1, 3};
36 int arrSize = sizeof(arr) / sizeof(arr[0]);
37 printf("%s\n", uniqueOccurrences(arr, arrSize) ? "true" : "false");
38 return 0;
39}In the C implementation using sorting, we use qsort to sort the frequency array and then check if any consecutive elements are equal.